网格中的最短路径 [英] Shortest path in a grid
问题描述
我有一个二维矩阵，如
A .........
## .... ## ..
。#### ... ##
..........
....... ###
B .........
#### ... ###
＃...＃。###。
其中'。'代表路径，'＃'表示wall.I必须找到从 A 指向 B 的最短路径。我熟悉 BFS 算法，并且它似乎是这个问题的一个合理的算法。但是，我发现它适用于网格是令人困惑的。任何人都可以在这个问题中使用一些伪代码来实现 BFS 算法吗？ 解决方案
BFS算法基本上是：
1 。排列源顶点并将其标记为
2 。虽然Q不是空的，重复3和4.
3 即可。执行deque和dequeed vertex x，do
4 。对于x的所有相邻顶点，这些顶点都没有被访问，并将它们标记为访问并将它们排入Q.
这就是基本算法，如果我们一步一步地去非常容易将这些步骤应用到网格中，唯一需要注意的是对于网格中的单元格，可能有8个邻居，并且我们必须在遍历邻居之前检查边界条件，以避免数组索引超出边界。
假设我们位于 A（a，b）的位置，我们想要达到 B（C，d）。我们遵循类似的4个步骤，但做了如下修改：
1 。制作2-d点数你可以用Java这样的语言轻松做到这一点，通过创建一类2-D点，然后创建该类的对象的类）
2 。创建一个二维数组 visited 大小为布尔类型的网格，初始化为false。
。制作一个二维数组<
让网格的大小为 nxm
现在伪代码如下：
排列A（a，b）到Q
Mark dist [a （Q不为空）
{
Point = p（deque（Q）$ b $）[b] = 0并访问[a] [b] = true
b
if（p匹配B（c，d））
{
print（从A到B距离[c] [d]是可能的路径）
return
}
else
{
//现在我们所要做的就是根据
//检查所有可能的邻居单元格到我们网格中的当前位置
//所以我们必须检查所有8个邻居单元
if（p.y <如果（grid [px] [py + 1]！='＃'和visited [px] [py + 1] == false）
{
{
enqueue（px，py + 1）to the Q // step s1
distance [px] [py + 1] = distance [px] [py] + 1 // step s2
visited [如果（px
if（grid [px] [py + 1] = true //步骤s3
}
}
（px + 1，py）重复步骤s1，s2，s3，
if（py> 0）
{
if（grid [px] [py - 1]！='＃'and visited [px ]
{
对于点（px，py - 1）
}
}
重复步骤s1，s2，s3 if （px> 0）
{
if（grid [px-1] [py]！='＃'and visited [px-1] [py] == false）
{
如果（px> 0且py> 0）
，重复步骤s1，s2，s3得到点（px-1，py）
}
}
{
if（grid [px - 1] [py - 1]！='＃并访问[px-1] [py-1] == false）
{
对于点（px-1，py-1）
} $ b重复步骤s1，s2，s3 $ b}
if（px> 0和p.y <如果（grid [px-1] [py + 1]！='＃'和visited [px-1] [py + 1] == false）
（
）如果（px< n-1，py> b）重复步骤s1，s2，s3得到点（px-1，py + 1）
}
}
， 0）
{
if（grid [px + 1] [py-1]！='＃'and visited [px + 1] [py - 1] == false）
{
如果（px
} 1）
{
if（grid [px + 1] [py + 1]！='＃'and visited [px + 1] [py + 1] == false）
{
为点（px + 1，py + 1）
}
}
}
}
重复步骤s1，s2，s3 print是不可能的）
I have a two dimensional matrix like
A.........
##....##..
.####...##
..........
.......###
B.........
####...###
#...#.###.
Where '.' represents path and '#' represents wall.I have to find the shortest path possible from point A to point B.I am familiar with BFS algorithm and it seems like a reasonable algorithm for the problem. But I find it confusing to apply on the grid.Can anyone suggest implementation of BFS algorithm in this problem with some pseudo-codes ?
The BFS algorithms is basically:
1.Enqueue the source vertex and mark it visited.
2.While the Q is not empty repeat 3 and 4.
3. Perform deque and the for the dequed vertex x, do
4. For all adjacent vertices of x, that are not visited and mark them visited and enqueue them to the Q.
So thats the basic algorithm, if we go step by step its very easy to apply these steps to grid,the only thing that we should be careful is for a cell in a grid there are 8 neighbours possible, and we must check the boundary conditions before traversing the neighbours, to avoid array index out of bounds.
Say we are at position A(a,b) and we want to reach B(c,d). We follow the similar 4 steps but with some modification as follows:
1.Make a Q of 2-d points,(You can do that easily in languages like Java, by making a class of 2-d points and then Q of objects of that class)
2.Make a 2-d array visited of size of grid of type boolean, initialized to false.
3.Make a 2-d array distance of size of grid of type integer, that will be used for the distance.
Let size of grid be nxm
Now the pseudocode is as follows:
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 )
这篇关于网格中的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
