输入样例:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
8
算法
这段C++代码使用宽度优先搜索(BFS)算法来解决给定迷宫问题,即找出从左上角(1,1)到右下角(n,m)的最短路径。以下是代码的详细解读:
n
和m
:分别表示迷宫的行数和列数。c[105][105]
:存储迷宫的二维数组,其中c[i][j]
表示迷宫中第i
行第j
列的值(0或1)。f[105][105]
:用于存储从起点到每个点的最短路径长度。初始化为一个很大的数(1e4
,即10000)。a
和b
:两个队列,分别用于存储BFS中待处理的点的x坐标和y坐标。dx
和dy
:分别表示上下左右四个方向的x和y坐标变化。
BFS函数
void bfs(int x,int y)
{
// …(函数内部代码)
}
这个函数用于执行宽度优先搜索。它从起始点(x, y)开始,并尝试向四个方向移动。对于每个可达的点,如果通过当前路径到达它的距离比之前记录的更短,则更新该点的最短路径长度,并将其加入队列以进行进一步的搜索。
主函数
int main()
{
// ...(函数内部代码)
}
- 首先,读入迷宫的行数和列数,以及迷宫本身。
- 调用
bfs(1, 1)
从起点开始搜索。 - 输出从起点到终点的最短路径长度(
f[n][m]
)。
代码执行流程大致如下:
1.初始化变量和数组。
2.读入迷宫尺寸和迷宫本身。
3.从起点(1, 1)开始BFS搜索。
4.在BFS过程中,不断更新每个点的最短路径长度。
5.当搜索到终点(n, m)时,停止搜索。
6.输出从起点到终点的最短路径长度。
7.在给定的输入样例中,迷宫的最短路径长度是8,因此输出也是8。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m,c[105][105],f[105][105];
queue<int>a,b;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs(int x,int y)
{
a.push(x);
b.push(y);
f[x][y]=0;
while(!a.empty())
{
int fx=a.front();
int fy=b.front();
for(int i=0;i<4;i++)
{
int nx=fx+dx[i];
int ny=fy+dy[i];
if(nx<=0||ny<=0||nx>n||ny>m||c[nx][ny]==1)
continue;
if(f[fx][fy]+1<f[nx][ny])
{
f[nx][ny]=f[fx][fy]+1;
a.push(nx);
b.push(ny);
}
}
a.pop();
b.pop();
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
f[i][j]=1e4;
}
}
bfs(1,1);
cout<<f[n][m];
return 0;
}