2

我有一个包含数字的二维数组。它可能是这样的：

11211
1  31
1 111
1  11
13111

数字 1 是“墙”，2 是入口，3 是我们想要到达的点。如您所见，我们有两次出现 3，而且它们的距离并不相等。我需要找到最近的一个。请记住，输入数组是随机的，不必看起来像这样。

我正在考虑如何解决它：首先找到入口。这只能在 O(n^2) （最坏情况）时间内完成，因为入口可能位于数组中的任何位置，而不必沿着边缘。我可以毫无问题地实现这一点。

然后我需要从数组的入口点开始搜索。每当我找到数字 3 时，我都需要记住我访问过它，以及点之间的距离（示例中的 2 和 3）。假设我找到离入口最远的 3 号。这显然不是最近的点（如果我们看这个例子）。我需要跳回入口并再次搜索。我想有一种实时计数器，计算步数，这样如果我比我刚刚找到的宝藏多走一步，我就会停下来说之前找到的宝藏是最近的。

我认为有一种更好的方法可以有效地实现它，但我真的想不出该怎么做。我尝试搜索 Dijkstra 的算法，但它似乎找到了从入口到数组中所有数字的最短路径（数字是目标数字 3）。我想你可以过滤掉它们中最短的，但是你将如何在 Java 中实现它呢？

我不是在寻找完整的代码，而只是在寻找可以指导我的东西，以便我了解如何实现它。

4

2 回答 2

4

假设“距离”是指在空旷的地方行走。

  1. 从入口开始，将元素向左、向上、向下和向右移动，如果已经标记为已访问，则不要进入。如果您看到一堵墙或撞到边缘，请将其标记为已访问并忽略它。如果您看到一个空白空间，请将元素放入队列中。

  2. 标记访问的入口。

  3. 从 (1) 中的队列中取出一个元素

  4. 使用出队的元素作为新的“入口”，重复 (1)-(3) 直到你点击 a 3，在这种情况下，停止。那3是离入口最近的地方

  5. 如果您没有遇到任何人3并且您已经在（1）中访问了所有内容，则意味着无法3从入口到达。

这是广度优先搜索的一个实例，使用类似于洪水填充的技术。

此外，当且仅当有多个3具有相同且最短的距离时，您在 (1) 中访问的方向可能会影响最终结果。

于 2013-04-28T15:27:23.550 回答
2

我喜欢贝尔曼福特解决这样的问题。当然它的 N^3 （在这种情况下），但它很容易实现。

http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

在你的情况下：

设置 创建一个二维数组 ShortestDistance 并用无穷大填充它。遍历数组并将 ShortestDistance 设置为 0，其中有门。这些是我们可以在 0 距离内到达的网格点。

算法

   For itr in 0 to N //（任何门与门之间的最大距离）
      for i in 0 to N // 行索引
         for j in 0 to N //列号
           如果 Grid[i][j] == 1
              继续; //它是一堵墙，它不能传播最短距离
           别的
               最短距离[i][j] = min(
                                           ShortestDistance[i][j], //当前值
                                           1 +（所有邻居之间的最短距离*）//减少的最短路径。

*在每一步中，我们都会通过到达其邻居之一的最短距离 + 1 或当前值本身来更新到达某个地点的最短距离。

后处理 遍历 ShortestDistance 2D 数组并打印对应于“3”类型点的最小值。

于 2013-04-29T02:21:17.517 回答