algorithm - 网格中的最短路径

Question

我有一个像这样的二维矩阵

A......... 
##....##..
.####...##
..........
.......###
B.........
####...### 
#...#.###.

其中 '.' 代表路径，'#' 代表墙。我必须找到从点 A 到点的最短路径B。我熟悉BFS 算法，它似乎是解决该问题的合理算法。但是我发现在网格上应用很困惑。有人可以建议用一些伪代码在这个问题中实现 BFS 算法吗？

Answer 1

BFS 算法基本上是:

1.将源顶点入队并标记它已访问。

2。当 Q 不为空时，重复 3 和 4。

3。执行双端队列和对于双端队列的顶点x，做

4。对于 x 的所有未访问的相邻顶点，将它们标记为已访问并将它们排入 Q。

这就是基本算法，如果我们一步一步地把这些步骤应用到网格中是很容易的，我们唯一要注意的是网格中的一个单元格有 8 个可能的邻居，我们必须检查遍历邻居前的边界条件，避免数组索引越界。

假设我们在位置A(a,b)，我们想到达B(c,d)。我们遵循类似的 4 个步骤，但进行了一些修改，如下所示:

1.制作一个二维点的 Q，(你可以用像 Java 这样的语言很容易地做到这一点，方法是制作一个二维点的类，然后制作一个对象的 Q那个类(class))

2.制作一个二维数组visited，大小为 bool 类型的网格，初始化为false。

3.制作一个二维数组distance，大小为整数类型的网格，将用于距离。

设网格大小为nxm

现伪代码如下:

Enqueue A(a,b) to the Q

Mark dist[a][b] = 0 and visited[a][b] = true

while( Q is not empty )
{
 Point p = deque(Q)

 if( p matches B(c,d) )
 {
   print( Yes path is possible from A to B with distance[c][d] )
   return
 }
 else
 {
  //Now all we have to do is check all the possible neighbour cells according
  // to our current position in the grid
  // So we have to check all the 8 neighbour cells
   if(p.y < m - 1)
   {
    if( grid[p.x][p.y + 1] != '#' and visited[p.x][p.y + 1] == false )
    {
     enqueue (p.x,p.y + 1) to the Q // step s1
     distance[p.x][p.y + 1] = distance[p.x][p.y] + 1 // step s2
     visited[p.x][p.y + 1] = true // step s3
    }
   }
   if(p.x < n - 1)
   {
    if( grid[p.x + 1][p.y] != '#' and visited[p.x + 1][p.y] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x + 1,p.y)
    }
   }
   if(p.y > 0)
   {
    if( grid[p.x][p.y - 1] != '#' and visited[p.x][p.y - 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x,p.y - 1)
    }
   }
   if(p.x > 0)
   {
    if( grid[p.x - 1][p.y] != '#' and visited[p.x - 1][p.y] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x - 1,p.y)
    }
   }
   if(p.x > 0 and p.y > 0)
   {
    if( grid[p.x - 1][p.y - 1] != '#' and visited[p.x - 1][p.y - 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x - 1,p.y - 1)
    }
   }
   if(p.x > 0 and p.y < m-1)
   {
    if( grid[p.x - 1][p.y + 1] != '#' and visited[p.x - 1][p.y + 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x - 1,p.y + 1)
    }
   }
   if(p.x < n-1 and p.y > 0)
   {
    if( grid[p.x + 1][p.y - 1] != '#' and visited[p.x + 1][p.y - 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x + 1,p.y - 1)
    }
   }
   if(p.x < n-1 and p.y < m-1)
   {
    if( grid[p.x + 1][p.y + 1] != '#' and visited[p.x + 1][p.y + 1] == false )
    {
     Repeat steps s1,s2,s3 for point (p.x + 1,p.y + 1)
    }
   }
 }     
}
print( the path is not possible )