algorithm - Haskell - 在笛卡尔网格中对特定的最近邻居进行分组

Question

我正在寻找这个难题的方向，我需要将特定的最近邻居组合在一起。

我的输入数据是:

myList :: Map (Int, Int) Int
myList =
  fromList
    [((-2,-2),0),((-2,-1),0),((-2,0),2),((-2,1),0),((-2,2),0)
    ,((-1,-2),1),((-1,-1),3),((-1,0),0),((-1,1),0),((-1,2),1)
    ,((0,-2),0),((0,-1),0),((0,0),0),((0,1),0),((0,2),0)
    ,((1,-2),0),((1,-1),0),((1,0),0),((1,1),2),((1,2),1)
    ,((2,-2),0),((2,-1),2),((2,0),0),((2,1),0),((2,2),0)]

这是这个 5 x 5 网格(棕色土地，蓝色水域)的数据表示:我使用 (Int,Int) 作为 XY 坐标，因为必须生成列表的方式(因此它的排序)在笛卡尔坐标网格上呈螺旋状(0,0) 是原点。剩余的 Int 是人口规模 0 是水域，1..9 是陆地。

由于我的 Map 的顺序，我一直在努力寻找一种方法来遍历我的数据并返回 4 分组的土地项目，这些土地项目是根据每个其他连接的接近度(包括对角线)，所以我正在寻找如下结果:

[ [(-1 , 2)]
, [(1, 2),(1,1)]
, [(-2, -0),(-1,-1),(-1,-2)]
, [(2, -1)]]

我已经研究并尝试了各种算法，例如 BFS、Flood Fill，但我的输入数据不符合结构要求，或者我对主题的理解不允许我将其转换为使用坐标。

有没有一种方法可以直接在数据上运行算法，或者我应该寻找另一个方向？

很抱歉，到目前为止我没有代码示例，但我什至无法创建任何远程有用的东西。

Answer 1

我建议使用联合查找数据结构。遍历所有位置；如果它是陆地，​​则将其标记为等同于紧邻它的 NE、N、NW 或 W 的任何位置，这些位置也是陆地。 (当你访问其他土地时，它会自动被标记为等同于存在于它的 E、SW、S 或 SE 的任何土地。集合 D={NE, N, NW, W} 的关键属性是，如果你镜像 D 中的所有方向以获得 M，则 M∪D 包含每个方向；具有此属性的任何其他集合 D 也可以。)此过程结束时数据结构返回的等价类将是您连接的土地 block 。

如果n是仓位总数，这个过程就是O(n*log n)； log n 分量来自确定邻居是陆地还是水域所需的 Map 查找。

如果可以的话，您应该考虑使 Map 变得稀疏——只存储对应于 land 的键值对并跳过 water 键——逐渐达到 O(m*log m) 其中m 是地的总数，而不是位置的总数。如果你不能(因为你必须记住水和不存在的位置之间的区别，比如说)，你可以考虑切换到一个数组作为你的后备存储，以升级到 O(n*a n)，其中 a 是反阿克曼函数，因此，整个 shebang 基本上将尽可能接近 O(n)，而不是实际 O(n)。

当 O(m*log m) 或 O(n*a n) 两者都是一个选项时，哪个更可取是对您认为代表您的典型用例的某些数据集进行实证探索的问题。