方矩阵遍历对具有相同值的相邻单元格进行分组

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) 的范围内16=] 例如。感谢您的帮助。提前致谢。

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 在此图上，您可以轻松找到一组具有相同值的坐标组合在一起。

希望对您有所帮助！

方矩阵遍历对具有相同值的相邻单元格进行分组

Square Matrix Traversal grouping adjacent cells with same values

python

algorithm

traversal

pseudocode

matrix