网格中的最短路径

Question

我有一个像

这样的二维矩阵

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

其中'.'代表路径，'#'代表wall.I必须从点找到可能的最短路径A指向B。我熟悉BFS算法，它似乎是一个合理的算法问题。但是我发现在 grid.Can 上应用令人困惑任何人建议在这个问题中使用一些伪代码实现 BFS 算法 ?

Answer 1

基本上，将每个点 (.) 视为一个节点，每两个相邻的点之间也应该有一条边*。这样你就得到了一个图表，其中包含路径可以经过的所有可能位置，并且它只包含有效边。

从那里很容易运行 BFS...

* 如果允许沿对角线移动，那么也应该添加那些边。这已经深入到 "neighbor".

的定义到底是什么了

Answer 2

BFS算法基本上是：

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

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

3。对dequed顶点x执行deque和the，do

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

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

假设我们在位置 A(a,b) 并且我们想要到达 B(c,d)。我们遵循类似的 4 个步骤，但有一些修改如下：

1。制作二维点的 Q，（您可以使用 Java 等语言轻松完成此操作，方法是制作 class 的二维点，然后是 class)

的对象的 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 )

网格中的最短路径

Shortest path in a grid

algorithm

graph

grid

shortest-path

breadth-first-search