寻找城市所连接的最大陆地的算法？

Question

我有一张世界地图的黑白照片。

我将像素转换为二进制值的网格（0表示水，1表示陆地），并按坐标(i, j)进行索引。现在，假设我在美国德克萨斯州的某个地方随机选择了一个陆地上的点，我想知道我可以到达的所有点的(i, j)坐标，而无需穿过水域。在这种情况下，它将是所有北美和南美的(i, j)（减去任何周围的岛屿）。

（背后的动机是我正在尝试用C语言并行实现SIR感染模型。）

非常感谢您的帮助。

编辑：如果有任何近似方法（如果不小心包括一些离岸小岛也不过分），我也会感兴趣，也许是通过类似四叉树的网格方法？再次感谢。

- mchen

---

尝试使用"泛洪填充"算法（flood fill）进行操作。 - irrelephant

看起来一个简单的泛洪算法就可以解决问题。有数十种实现可供选择。 - Clinton Pierce

Answer 1

你正在寻找一种 泛洪填充算法。它可以通过递归方式、手动维护堆栈或使用队列来实现。

- Thomas

---

谢谢@Thomas，我看了一下这个算法，但据我所知，它基本上是进行逐像素检查，这似乎很慢。如果我可以容忍一些误差（即不太在意是否包括一些微小的离岸岛屿），是否有基于网格方法的算法，例如通过四叉树？ - mchen

你是否真的尝试过它的速度是否足够快？这只检查每个像素至多一次，因此它在像素数量上是线性的。由于您要求获取可以到达的所有点的坐标，因此不能更有效地完成此操作（在一般情况下，像素数量也是线性的）。如果您需要执行大量此类查找，则可以将地图预处理为连接组件，并在常数时间内回答查找。 - Thomas

再次感谢。您知道有并行实现的方法吗？使用MPI或OpenMP（或两者都可以）都可以。谢谢。 - mchen