网格中的最短路径

2 回答

• 1

  BFS算法基本上是：

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

  2 . 虽然Q不为空，重复3和4 .

  3 . 执行deque和dequed vertex x，do

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

  这就是基本算法，如果我们一步一步地将这些步骤应用到网格中，我们应该特别注意的是网格中的单元格可能有8个邻居，我们必须检查边界条件在遍历邻居之前，避免数组索引超出范围 .

  假设我们处于 A(a,b) 位置，我们希望达到 B(c,d) . 我们遵循类似的4个步骤，但有一些修改如下：

  1 . 制作一个2-d点的Q，（你可以用Java等语言轻松完成，通过制作一个2-d点，然后是该类对象的Q）

  2 . 使用boolean类型的网格大小的2-d数组 visited ，初始化为false .

  3 . 制作一个2-d数组 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 )
  

  回复于 2024-05-08T13:26:23+08:00
• 2

  非常基本上，将每个点（ . ）视为一个节点，并且作为邻居的每两个点也应该在它们之间具有边缘 * . 通过这种方式，您可以获得一个图表，其中包含路径可以通过的所有可能位置，并且它仅包含有效边 .

  从那里开始运行BFS非常容易......

  * 如果允许您沿对角线移动，则还应添加这些边缘 . 这已经进入了"neighbor"的确切定义 .

  回复于 2024-05-08T13:26:23+08:00