检查网格中瓷砖的相邻性

Question

我正在研究 sliding block puzzle 解算器，我想将游戏扩展到具有任意边和各种形状块的网格。我定义了一个具有给定高度和宽度的网格，并将其转换为一个字典，其中以运行索引作为键，以布尔值作为值（如果平铺则为真，否则为假）。

带有运行索引的示例：

|0|1|2|
|3|4|5|
|6|7|8|

示例块及其对应的字典（Xs 表示平铺位置）

|0|1|X|
|3|X|X|
|X|X|8|

{
   0: false, 1: false, 2: true,
   3: false, 4: true,  5: true,
   6: true,  7: true,  8: false
}

因为我打算随机创建块布局，所以我想测试任意布局的有效性。块有效的要求之一是所有块都通过相邻的邻居连接。

有效区块：

|X|X|X|
|X| |X|
|X| | |

无效块（块1和5未连接）：

|X|X| |
| | |X|
| | |X|

起初，我认为我可以通过获取块中每个平铺位置的相邻索引列表并检查是否每个其他平铺索引都包含在至少一个邻接列表中来解决这个问题。但是上面的无效示例已经是行不通的情况了。

我如何检查所有的图块是否以某种方式相互连接？

PS：这个问题似乎与我使用的语言无关，但由于我使用的是 C#，所以我会添加该标签以确保万无一失。

Answer 1

您可以从任何一个图块开始，运行一个DFS（深度优先搜索）。如果您可以在 DFS 期间访问所有的磁贴，则您的磁贴已连接。否则不是。

这是一个伪代码

dfs(x,y):
   visited[x][y] = true
   for each position in your adjacency list: ## up,down,left,right
      if(visited[newX][newY]==false and grid[newX][newY] is a tile and newX , newY both is in the grid ):
          dfs(newX,newY)

基本上只是从一个瓷砖开始，只移动到另一个瓷砖使用左/右/上/下移动只要有可能的。如果它们没有连接，您将在访问每个磁贴之前结束。

检查网格中瓷砖的相邻性

Check adjacency of tiles in a grid

c#

algorithm

sliding-tile-puzzle