AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
wjie
,
2020-07-01 20:38:35
,
所有人可见
,
阅读 504
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 205;
char arr[N][N];
int n, m, st[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
struct Node{
int x, y, step;
}start;
int bfs()
{
queue<Node> q;
q.push(start);
st[start.x][start.y] = 1;
while (q.size())
{
Node now = q.front();
q.pop();
if (arr[now.x][now.y] == 'E') return now.step;
for (int i = 0; i < 4; ++i)
{
int nx = now.x + dx[i], ny = now.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !st[nx][ny] && arr[nx][ny] != '#')
{
st[nx][ny] = 1;
q.push({nx, ny, now.step+1});
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(st, 0, sizeof st);
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
{
scanf("%s", arr[i]);
for (int j = 0; j < m; ++j)
{
if(arr[i][j] == 'S')
start = {i, j, 0};
}
}
int t = bfs();
if (t == -1) puts("oop!");
else printf("%d\n", t);
}
return 0;
}