2D数组，所有值相邻 [英] 2d array, all values are adjacent

问题描述

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

I need a fast way to check if a 2d array is entirely adjacent, meaning all values are adjacent to other same values. Adjacent means the four cardinal directions.

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）方法，该方法遍历整个数组并检查是否至少有一个邻居是相同的值。我正在寻找一种可能更快的方法。

So far, I've tried an O(M * N) method where I go through the whole array and check if at least one of the neighbors is the same value. I'm looking for a possibly faster way.

编辑：只是注意到我的方法甚至无法正常工作。例如：

just noticed my method doesn't even work correctly. eg:

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

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

So now I need an actual algorithm for this.

推荐答案

我想起了Minesweeper游戏。

I'm reminded of the game Minesweeper.

1. 外循环：扫描整个数组（从左到右逐行）。
   这是查找内循环的下一个位置。如果我们没有从内部循环中访问
   到该位置，并且尚未看到位于该位置的
   的数字，则从该
   位置开始内部循环。如果我们已经在该位置看到了数字，则
   的矩阵不是相邻的。

1. Outer loop: Scan the entire array (row by row, from left to right). This is to find the next position for the inner loop. If we have not visited this position from the inner loop, and the number at this position has not yet been seen, start the inner loop at this position. If we have already seen the number at this position, then the matrix is not "adjacent".

内循环：查找包含以下内容的所有相邻单元格：相同的数字，并将它们标记为
作为访问者（扫雷的部分）。将这个数字记录为
访问并返回到外部循环。

Inner loop: Find all adjacent cells with the same number and mark them as visited (the Minesweeper part). Record this number as visited and return to the outer loop.

这需要一个布尔矩阵，其中显示 已访问位置（与要扫描的数组大小相同）和已访问过的数字[1..n]的布尔列表。

This requires a boolean matrix showing "visited" positions (the same size as the array being scanned) and a boolean list of numbers [1..n] that have been "visited".

这篇关于2D数组，所有值相邻的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！