AcWing 844. 走迷宫
原题链接
简单
作者:
GK50
,
2024-03-02 09:39:08
,
所有人可见
,
阅读 16
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PIL;
const int N = 110;
int s[N][N];
int dp[N][N];
int path[N][N];
int n,m;
int bfs(){
queue<PIL> p;
p.push({1,1});
path[1][1]=1;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int x,y;
while(!p.empty()){
PIL a = p.front();
p.pop();
x = a.first;
y = a.second;
for(int i = 0;i < 4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= n && ny >=1 && ny <= m && !s[nx][ny] && !path[nx][ny]){
path[nx][ny] = 1;
dp[nx][ny] = dp[x][y] + 1;
p.push({nx,ny});
}
}
}
return dp[n][m];
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> s[i][j];
}
}
cout << bfs() << endl;
return 0;
}