2

我遇到的问题类似于此处发现的问题：https ://www.geeksforgeeks.org/find-size-of-the-largest-formed-by-all-ones-in-a-binary-matrix/

不同之处在于“+”必须使矩阵中的所有其他单元格为零。例如：

00100  
00100   
11111   
00100   
00100

这将是一个 5x5 矩阵，有 2 个“+”，一个在另一个里面。

另一个例子：

00010000  
00010000  
00010000  
11111111  
00010000  
00010010
00010111
00010010

这个矩阵是 8x8，将有 3 个“+”，其中一个是右下角的小 3x3 矩阵，另外 2 个是由 5x5 矩阵形成的，一个内一个，类似于第一个示例。

使用上面链接中的代码，我只能到目前为止：

M = [[0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1],
     [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1, 0],
     [0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 0, 0, 1, 0]]
R = len(M)
N = len(M)
C = len(M[0])
left = [[0 for k in range(C)] for l in range(R)]
right = [[0 for k in range(C)] for l in range(R)]
top = [[0 for k in range(C)] for l in range(R)]
bottom = [[0 for k in range(C)] for l in range(R)]
for i in range(R):
    top[0][i] = M[0][i]
    bottom[N - 1][i] = M[N - 1][i]
    left[i][0] = M[i][0]
    right[i][N - 1] = M[i][N - 1]
for i in range(R):
    for j in range(1,R):
        if M[i][j] == 1:
            left[i][j] = left[i][j - 1] + 1
        else:
            left[i][j] = 1
        if (M[j][i] == 1):
            top[j][i] = top[j - 1][i] + 1
        else:
            top[j][i] = 0
        j = N - 1 - j
        if (M[j][i] == 1):
            bottom[j][i] = bottom[j + 1][i] + 1
        else:
            bottom[j][i] = 0
        if (M[i][j] == 1):
            right[i][j] = right[i][j + 1] + 1
        else:
            right[i][j] = 0
        j = N - 1 - j
n = 0
for i in range(N):
    for j in range(N):
        length = min(top[i][j], bottom[i][j], left[i][j], right[i][j])
        if length > n:
            n = length
print(n)

目前，它返回“+”最长边的输出。所需的输出将是方阵中“+”的数量。

我无法检查矩阵中的所有其他单元格是否为零，如果整个矩阵中有一个，则无法找到单独的“+”。

任何帮助是极大的赞赏。

4

1 回答 1

0

我不想破坏解决这个问题的乐趣，所以这里不是一个解决方案，而是一些提示：

  1. 尝试编写一个子例程（一个函数），给定一个方阵作为输入，决定这个输入矩阵是否是“+”（假设函数返回一个“1”，如果它是一个“+”和一个'0' 否则）。
  2. 从 1. 修改函数，以便您可以将其作为输入完整矩阵的子矩阵（您要在其中计算“+”）。更具体地说，输入可以是子矩阵左上角的坐标及其大小。返回值应与 1 相同。
  3. 您能否编写一个循环来检查给定矩阵的所有子矩阵并使用 2. 中的函数计算“+”的子矩阵？

这里有一些小评论：这导致的算法在多项式时间内运行（在输入矩阵的维度上），所以基本上它不应该花很长时间。我没有想太多，但可能算法可以更高效。此外，您也许应该考虑是否将被“0”包围的“1”算作“+”。

于 2018-10-05T13:04:18.030 回答