AcWing 1099. 仙岛求药
原题链接
简单
作者:
成为一个优秀的人
,
2021-12-06 19:10:25
,
所有人可见
,
阅读 173
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int>PII;
typedef pair<PII,int>PIII;
const int N = 305;
char g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m;
int x, y;
int bfs(){
queue<PIII>q;
q.push({{x, y}, 0});
g[x][y] = '#';
while(q.size()){
PIII st = q.front();
q.pop();
PII u = st.first;
int dist = st.second;
for(int i = 0; i < 4; i ++ ){
int a = dx[i] + u.first, b = dy[i] + u.second;
if(a >= 0 && b >= 0 && a < n && b < m && g[a][b] != '#'){
q.push({{a, b}, dist + 1});
if(g[a][b] == '*') return dist + 1;
g[a][b] = '#';
}
}
}
return -1;
}
int main(){
while(cin>>n>>m, n && m){
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ ){
cin>>g[i][j];
if(g[i][j] == '@') x = i, y = j;
}
cout<<bfs()<<'\n';
}
return 0;
}