2

我有一个用于移动应用程序的棋盘游戏，显示在此链接中：http: //i45.tinypic.com/23u8u1h.png

起点可以是任何单元格。获胜者是垂直（绿色玩家）或水平（红色玩家）连接他/她的人。

节点是彩色单元格。白细胞可以被认为是重量吗？我不知道如何实现它，但是当我想到 Dijkstra 算法时，我相信当板子处于这种状态时，它需要花费很多时间来计算直到它得到正确的答案：http://i50。 tinypic.com/35ivofd.png（我必须在这四个绿色单元格上应用算法）

我想要一种算法，它告诉我“ http://i48.tinypic.com/28c2ijl.png ”黑色、棕色、蓝色和紫色路径是合理时间内最短的路径。

提前致谢。

4

1 回答 1

0

我认为 Dijkstra 在这里工作得很好，特别是与用于连接彼此相邻的字段并填充白色以外的颜色的联合查找算法结合使用。通向白场的边花费 1，通向己方场的边花费 0，通向敌方场的边花费无穷大（例如mn）。然后，您不会在代表单个字段的节点上运行 Dijkstra，而是在这些字段的联合（非白色字段的集群）上运行。

Dijkstra 将在这里工作大约O(mn log^2(mn))，其中n和m是棋盘的尺寸，Union Find 将在O(log mn)时间内通过简单的优化工作，在链接的底部提到文章。

于 2012-10-06T11:14:50.850 回答