algorithm - 如何查找矩阵中唯一直线的数量

Question

我们得到了一个大小为 M * N 的矩阵，矩阵每个位置内的值表示为一个点。我们必须找到可以通过 2 个或更多点绘制的唯一直线的数量。 例如。 M=2，N=2

*   *

*   *

可以绘制的唯一线条数为 6。

类似M=2,N=3

*    *    *

*    *    *

可以绘制的唯一线条数为 11。

我无法找到解决此问题的方法。请帮忙。

Answer 1

我认为既然在 Google 上找不到这样的问题，那么值得回答。这当然是一个有趣的问题，但下次尝试自己提供一些代码。

这是我的解决方案(原谅我的 python 有点生疏)

def notDiagonal(path):
    point1, point2 = path
    a1, a2 = point1
    b1, b2 = point2
    if(a1 == b1):
        return True
    if(a2 == b2):
        return True
    else:
        return False

N, M = 4, 2
matPoints, matPairs, bounds, edges = [], [], [], [(0,0),(N-1,0),(0,M-1),(N-1,M-1)]

def oneEdge(path):
    point1, point2 = path
    if (point1 not in edges and point2 not in edges) or (point1 in edges and point2 in edges):
        return False
    return True

for i in range(N):
    if (i,0) not in bounds:
        bounds.append((i,0))
    if (i,M-1) not in bounds:
        bounds.append((i,M-1))
    for j in range(M):
        matPoints.append((i, j))

for j in range(M):
    if (0,j) not in bounds:
        bounds.append((0,j))
    if (N-1,j) not in bounds:
        bounds.append((N-1,j))        

print("number of points is: ", len(matPoints))

for i in range(len(matPoints)-1):
    for j in range(i+1, len(matPoints)):
        matPairs.append(  ( matPoints[i], matPoints[j]  )   )
matPairCopy = list(matPairs)

print("number of lines before removal: ", len(matPairs))

for i in range(len(matPairs)):

    a = (matPairs[i][0][0] + matPairs[i][1][0])/2.0
    b = (matPairs[i][0][1] + matPairs[i][1][1])/2.0

    if(int(a) == a and int(b) == b):

            # Center point is (int(a), int(b))
            # Delete the partitioned lines if they exist (they may have been deleted before)

            if(  ((matPairs[i][0][0], matPairs[i][0][1]),   (int(a), int(b))) in matPairCopy):
                matPairCopy.remove(   ((matPairs[i][0][0], matPairs[i][0][1]),   (int(a), int(b)))    )
            if(  ((int(a), int(b))  ,  (matPairs[i][1][0], matPairs[i][1][1])   ) in matPairCopy     ):
                matPairCopy.remove(   ((int(a), int(b))  ,  (matPairs[i][1][0], matPairs[i][1][1])   ))

for k in matPairs:
    if(k[0] not in bounds or k[1] not in bounds):
        if(k in matPairCopy):
            matPairCopy.remove(k)
    elif(notDiagonal(k) and (oneEdge(k)) and k in matPairCopy):
                matPairCopy.remove(k)

print("number of lines after removing partitions: ",  len(matPairCopy))

已编辑:修复了小问题

N = 2，M = 2:输出 = 6

N = 2，M = 3:输出 = 11

N = 2，M = 4:输出 = 18

N = 3，M = 3:输出 = 20

N = 3，M = 4:输出 = 31