c - 通过二维数组中的障碍物(地雷)的最短路径(C 编程)

Question

我有一个 C 程序的问题，其中给出了一个带有地雷的二维数组(地雷 = 数组字段设置为 1)。我需要找到从 (0,0) 到 (x-1,y-1) 的最短路径，并且您只能在 4 个方向(上、下、左、右)上移动。

您有什么想法吗？算法应该是什么样子才能使程序相当简单？

Answer 1

A* 和 Dijkstra 比您解决此问题所需的复杂得多，因为在您正在搜索的图中，所有边(网格正方形之间的步长)的权重均为 1。

只需使用广度优先搜索:

Let Q be a queue of (x,y) pairs
Let V be a set of (x,y) pairs.
Add the start point (x0,y0) to Q.
While Q is not empty
  H = Q.get_head
  for each neighbor pair N of H in the grid
    if N is not in V
      add N to V
      if N is the goal
        Return N. The path is the chain of N.prev references
      N.prev = H
      Q.add_to_tail(N)
Return "goal could not be reached"