0

我有一个二维数组，我想从一个点开始遍历到另一个点，并具有以下约束：

  • 只允许水平和垂直方向移动
  • 路径必须触及数组内的每个强制点
  • 阵列没有障碍物

这是一个图形表示：

+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | E |
+---+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+
| S | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+

从点 S 开始，算法应该能够找到到达 E 的最短路径，接触所有以“1”表示的点，并且只能水平或垂直移动。

我必须用 Javascript 来实现它（但即使在 C# 或 Java 中也应该不错，我想我可以翻译它:)）

哪种算法最适合我的需求？我用谷歌搜索了很多，但只发现了一些相似但不同的 Dijkstra 或 A 星实现（它们不必触及强制性点......）

有人遇到过这样的问题吗？

有人可以帮忙吗？

先感谢您

4

1 回答 1

0

好的，抱歉回复晚了。我想你可能已经得到了一些实现。如果没有，请考虑一下。

让我先做一个简单的版本。让我们假设 S 和 E 在它们各自的列中要么是最顶部的，要么是最底部的。有问题的问题图片符合这一点。

该算法应该：

  1. 向上（向下）移动列，直到达到（当前列顶部，下一列顶部）的最大值。
  2. 过渡到下一列。下一列成为当前列。
  3. 向下移动列，直到达到（当前列底部，下一列底部）的最大值

需要考虑的事项

  1. 您可以在行上运行算法。
  2. 最后一行/列需要以不同方式处理。
  3. 最后一行/列和第一行/列可能需要遍历两次。
  4. 如果 S 和 E 在行/列的中间，则需要修改。

PS我记得在某处做这个算法问题。如果我找到某个地方，将发布源代码。

于 2013-04-27T06:36:45.660 回答