AcWing 844. 走迷宫
原题链接
简单
作者:
洛师木木说
,
2021-01-12 21:31:45
,
所有人可见
,
阅读 315
走迷宫I
由寒假每日一题的延伸
- 我初次看着道题时的第一感觉使用bfs来求最最短路径的一道题,这也可以作为一道模板题了
/*总体思想是宽搜,因为宽搜可以求最小路径*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
int m,n; //定义 行 和 列
int g[N][N];
typedef pair<int, int> PII; //定义一个队列
int d[N][N];
//定义四个方向
int dx[4] ={1,0,-1,0}, dy[4] = {0,1,0,-1};
int bfs(){
queue<PII>t;
t.push({0,0});
// 初始化d数组
// memset(d, -1, sizeof(d));
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
d[i][j] = -1;
}
}
d[0][0] = 0;
// 队列不为空就循环
while(t.size()){
PII a = t.front(); //取出队头的元素
t.pop(); //出队
for(int i =0;i<4;i++){
int q = a.first+dx[i],p = a.second +dy[i];
if(q >= 0 && q<m && p>=0 && p<n && g[q][p] == 0 && d[q][p]==-1){
d[q][p] = d[a.first][a.second] + 1;//当前点到起点的距离
t.push({q, p});//将新坐标入队
}
}
}
return d[m-1][n-1];
}
int main(){
cin>>m>>n;
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
cin>>g[i][j];
}
}
cout<<bfs()<<endl;
}