algorithm - 网格中的最短路径

我有一个二维矩阵

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

其中,“.”表示路径,“”表示墙。我必须找到从A点到B点的最短路径。我熟悉BFS算法,这似乎是解决问题的合理算法。但是我觉得在网格上应用是很混乱的,有人能建议用一些伪代码来实现这个问题中的bfs算法吗?

最佳答案

基本上,bfs算法是:
1.将源顶点排队并将其标记为已访问。
2.当q不为空时,重复3和4。
三。执行deque和对于dequed顶点x的,do
四。对于x的所有相邻顶点,不被访问,并将其标记为已访问,并将其排队到q。
所以这就是基本的算法,如果我们一步一步地把这些步骤应用到网格上,我们唯一要注意的是网格中的一个单元可能有8个邻居,我们必须在遍历邻居之前检查边界条件,避免数组索引越界。
假设我们在A(a,b)位置,我们想到达B(c,d)。我们遵循类似的4个步骤,但做了如下修改:
1.对二维点做一个q(在Java这样的语言中,你可以很容易地做到这一点,先做一个二维点的类,然后再做一个该类对象的q)
2.创建一个二维数组visited布尔型网格大小,初始化为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 )