AcWing 1099. 仙岛求药
原题链接
简单
作者:
一抹斜阳
,
2019-12-14 19:54:58
,
所有人可见
,
阅读 935
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int m, n;
const int MAX = 301;
int a = 0, b = 0;
bool used[MAX][MAX];
char maze[MAX][MAX];
struct point
{
int x, y;
int d;
point(int x1, int y1, int d1) :x(x1), y(y1), d(d1)
{}
};
int bfs();
int main()
{
int i, j;
while (cin >> m >> n)
{
memset(used, false, sizeof(used));
if (m == 0 && n == 0)
break;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
cin >> maze[i][j];
if (maze[i][j] == '@')
{
a = i;
b = j;
}
}
cout << bfs() << endl;
}
return 0;
}
int bfs()
{
queue<point> q;
q.push(point(a, b, 0));
used[a][b] = true;
while (!q.empty())
{
point p = q.front();
q.pop();
if (maze[p.x][p.y] == '*')
return p.d;
else
{
if (p.x - 1 >= 1 && maze[p.x - 1][p.y] != '#' && !used[p.x - 1][p.y])
{
used[p.x - 1][p.y] = true;
q.push(point(p.x - 1, p.y, p.d + 1));
}
if (p.x + 1 <= m && maze[p.x + 1][p.y] != '#' && !used[p.x + 1][p.y])
{
used[p.x + 1][p.y] = true;
q.push(point(p.x + 1, p.y, p.d + 1));
}
if (p.y - 1 >= 1 && maze[p.x][p.y - 1] != '#' && !used[p.x][p.y - 1])
{
used[p.x][p.y - 1] = true;
q.push(point(p.x, p.y - 1, p.d + 1));
}
if (p.y + 1 <= n && maze[p.x][p.y + 1] != '#' && !used[p.x][p.y + 1])
{
used[p.x][p.y + 1] = true;
q.push(point(p.x, p.y + 1, p.d + 1));
}
}
}
return -1;
}