AcWing 1099. 仙岛求药
原题链接
简单
作者:
小.bug
,
2022-05-20 16:33:08
,
所有人可见
,
阅读 119
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N = 310;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,-1,0,1};
char g[N][N];
bool st[N][N];
int d[N][N];
int n, m;
int sx, sy, gx, gy;
int bfs()
{
memset(st,0,sizeof st);
memset(d,0x3f,sizeof d);
d[sx][sy] = 1;
st[sx][sy] = true;
queue<pii> q;
q.push({sx,sy});
while(q.size())
{
pii t = q.front();
q.pop();
for(int k = 0; k < 4; k++)
{
int nx = t.x + dx[k], ny = t.y + dy[k];
if(nx == gx && ny == gy) return d[t.x][t.y];
if(nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if(!st[nx][ny] && g[nx][ny] == '.')
{
q.push({nx,ny});
st[nx][ny] = true;
d[nx][ny] = d[t.x][t.y] + 1;
q.push({nx,ny});
}
}
}
}
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] == '@') sx = i, sy = j;
if(g[i][j] == '*') gx = i, gy = j;
}
}
cout << bfs() << endl;
}
return 0;
}