python - 方阵遍历将具有相同值的相邻单元格分组

Question

给定一个样本方阵 (0,1)，如下所示：

0 1 1 0 0 0
0 0 1 0 0 1
0 0 0 1 0 1
1 0 0 0 0 1
0 1 0 0 0 1
1 0 0 1 0 0

期望输出将是值等于 1 的单元组的数量。例如，上述矩阵的输出将是：

Group #1: (0,1), (0,2), (1,2), (2,3)
Group #2: (1,5), (2,5), (3,5), (4,5)
Group #3: (3,0), (4,1), (5,0)
Group #4: (5,3)

我目前的算法如下：

for i = 0, i < matrix.dimension, i++
   for j = 0, j < matrix.dimension, j++
       if (i,j),(i,j+1),(i,j-1),(i-1,j),(i-1,j+1),(i-1,j-1),(i+1,j),(i+1,j+1),(i+1,j-1) = 1 
           push all pairs of i, j = 1 into a group

但是后来我被困在如何将(2,3)和(2,5)分成两组，因为例如，(i+/-1, j+/-1)如果我遍历到单元格，它们仍在范围内(2,4)。感谢您的帮助。提前致谢。

标签： pythonalgorithmmatrixtraversalpseudocode

Answer 1

您可以将此矩阵可视化为图形。所以在每个坐标(x,y)上，这个点都连接到其他 8 个点，即

(x+1, y), (x+1,y-1), (x+1,y+1), (x,y+1), (x,y-1), (x-1,y), (x-1,y+1), (x-1,y-1).

所以你的点(x,y)会和上面的8个点相连。现在，您面前已经准备好了一张图表。

现在DFS在此图上运行，您可以轻松找到组合在一起的具有相同值的坐标集。

希望这可以帮助！