algorithm - 二维数组，所有值都是相邻的

Question

我需要一种快速方法来检查二维数组是否完全相邻，这意味着所有值都与其他相同值相邻。相邻是指四个主要方向。

This would be an adjacent array
[1 1 2]
[1 2 2]
[3 3 3]

This isn't
[1 2 1]
[1 2 2]
[3 3 3]

This is
[1 2 4]
[1 2 2]
[3 3 3]

到目前为止，我已经尝试了一种 O(M * N) 方法，我遍历整个数组并检查是否至少有一个邻居具有相同的值。我正在寻找一种可能更快的方法。

编辑:刚刚注意到我的方法甚至不能正常工作。例如:

This should fail (not all of the 1s are adjacent)
[1 2 1]
[1 2 1]
[3 3 3]

所以现在我需要一个实际的算法。

Answer 1

我想起了扫雷游戏。

1. 外层循环:扫描整个数组(逐行，从左到右)。这是为内循环寻找下一个位置。如果我们有没有从内部循环访问过这个位置，并且数字在这个位置还没有看到，在这个开始内循环位置。如果我们已经看到这个位置的数字，那么矩阵不“相邻”。

2. 内循环:找到所有相邻的单元格，并标记相同的数字他们访问过(扫雷部分)。将此号码记录为访问并返回外循环。

这需要一个显示“已访问”位置的 bool 矩阵(与被扫描的数组大小相同)和一个已“访问”的数字 [1..n] 的 bool 列表。