AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
CarpeDime
,
2021-02-05 21:46:14
,
所有人可见
,
阅读 346
#include <cstdio>
#include <cstring>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 210;
int n, m;
char maze[N][N];
int dist[N][N];
PII start;
bool in(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs() {
queue<PII> q;
q.push(start);
memset(dist, -1, sizeof dist);
dist[start.first][start.second] = 0;
// 逆时针
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
while (q.size()) {
PII t = q.front();
q.pop();
for (int i = 0; i < 4; ++ i) {
int x = t.first + dx[i];
int y = t.second + dy[i];
if (in(x, y) && maze[x][y] != '#' && dist[x][y] == -1) {
dist[x][y] = dist[t.first][t.second] + 1;
if (maze[x][y] == 'E') {
return dist[x][y];
}
q.push({x, y});
}
}
}
return -1;
}
int main() {
int T;
scanf("%d", &T);
while ( T -- ) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++ i) {
scanf("%s", maze[i]);
for (int j = 0; j < m; ++ j) {
if (maze[i][j] == 'S') start = {i, j};
}
}
int res = bfs();
if (res == -1) puts("oop!");
else printf("%d\n", res);
}
}