从颜色网格生成邻接表

Question

我在网上找不到与此类似的内容。我有一个具有多种颜色的网格，用 0 到 N 表示。因此，例如，图形可能如下所示：

0 0 1 1 1 2 2
0 1 1 1 1 1 1
1 1 3 3 3 4 4
1 1 3 4 4 4 4

我想在显示哪些连接的邻接列表中表示它。这看起来很简单很常见，但是我在网上找不到解决方法。

因此结果列表如下所示：

0: 1
1: 0, 2, 3, 4
2: 1
3: 1, 4
4: 3, 1

我的想法是从左上角到右下角遍历整个网格，检查东西南北颜色是否不同，然后将边添加到邻接表中。我不知道这是否是一个好的算法（我期望使用 floodfill，但我认为我不需要它）。希望这里的专家能给我一个更好的算法或者确认这个算法是可行的。

Answer 1

您的 'algorithm' 需要更多详细信息，但似乎基本上是正确的。

类似问题详见 ( https://github.com/JamesBremner/PathFinder/wiki/Hills ) 在正交网格中查看高度（而不是颜色。）

您可以查看读取网格并创建邻接矩阵的 C++ 代码 starting here 我希望您可以将其移植到 java 并根据您的特定需求进行调整。

Answer 2

一个简单的解决方案是从左上角迭代到右下角。对于给定的单元格，您检查两个相邻的单元格：右边的一个和下面的一个。假设网格的左上角坐标为 (0,0)，右下角坐标为 (m,n)。然后当你在单元格 (i,j) 时，你检查邻居：(i+1,j) 和 (i,j+1)。维护一个哈希图来跟踪您的邻接列表。设 c_i,j 为单元格 (i,j) 的颜色。您将添加的每次迭代： adjacencyMap.get(c_i,j).add(c_i,j+1) 和 colorMap.get(c_i,j+1).add(c_i,j) 当你在 (i,j) 并且检查 (i+1,j) 时。与 (i,j) 和 (i,j+1) 类似。

注意：我不确定您是否也考虑对角线上的邻居。如果是这种情况，您还要检查 (i,j) 和 (i+1,j+1)。

从颜色网格生成邻接表

Generate adjacency list from grid of colors

java

graph