题目描述
给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。
最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问,该人从左上角移动至右下角 (n,m) 处,至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。
输出格式
输出一个整数,表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
样例
输入样例:
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
算法
(bfs宽度优先搜索)
利用栈的思想,对已存储的地图进行宽度优先搜索,同时定义一个数组d用于记录当前所在位置距离起点的长度。首先,站在起点上,将起点(0,0)入队。while循环反复遍历队列,每次将对头元素拿出,并向四个方向遍历它的邻接点,将所有符合要求的点(x,y)入队。即:当前点不越界、可以走,并且没被走过。
同时记录当前入队点在d数组中的距离为走过来的那个点的距离+1
最后输出终点距离d[n-1][m-1]
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int g[N][N],d[N][N];
int n,m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int bfs()
{
queue<PII> que;
memset(d, -1, sizeof d);
d[0][0]=0;
que.push({0,0});
while(!que.empty())
{
auto t=que.front();
for(int k=0;k<4;k++)
{
int x=t.first+dx[k];
int y=t.second+dy[k];
if(x>=0&&x<n&&y>=0&&y<m&&!g[x][y]&&d[x][y]==-1)
{
que.push({x,y});
d[x][y]=d[t.first][t.second]+1;
}
}
que.pop();
}
return d[n-1][m-1];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) cin>>g[i][j];
cout<<bfs()<<endl;
return 0;
}