复习版
#include <iostream>
#include <cstring>
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
const int N = 210;
struct Coordinate {
int x, y;
} q[N * N];
int t, m, n, sx, sy;
char board[N][N];
inline int BFS(void) {
int front = 0, rear = 0;
*(q + rear++) = {sx, sy};
board[sy][sx] = '#';
constexpr int dirs[] {0,-1,0,1,0};
int steps = 0;
while (front < rear) {
size_t s = rear - front;
while (s--) {
const int x = (*(q + front)).x, y = (*(q + front)).y; ++front;
f(d, 0, 4) {
const int nx = x + dirs[d], ny = y + dirs[d + 1];
if(not(board[ny][nx] == '.' or board[ny][nx] == 'E')) continue;
if (board[ny][nx] == 'E') return steps + 1;
*(q + rear++) = {nx, ny};
board[ny][nx] = '#';
}
}
++steps;
}
return -1;
}
inline void print_board(void) {
putchar(10);
f(y, 1, m + 1) f(x, 1, n + 1) printf("%c%c", *(*(board + y) + x), x == n ? 10 : 32);
}
int main() {
cin >> t;
while (t--) {
memset(board, 0x0000, sizeof board);
cin >> m >> n;
f(y, 1, m + 1) f(x, 1, n + 1) {
cin >> board[y][x];
if (board[y][x] == 'S') sx = x, sy = y;
}
// print_board();
int ans = BFS();
if (ans == -1) puts("oop!");
else printf("%d\n", ans);
}
return 0;
}
BFS Algorithm $O(N * M)$
#include <iostream>
#include <queue>
using namespace std;
const int N = 210;
char g[N][N];
int T, m, n, sx, sy;
using P = pair<int, int>;
static constexpr int dirs[] {0, -1, 0, 1, 0};
int bfs(int sx, int sy) {
queue<P> q;
q.emplace(sx, sy);
g[sy][sx] = '#'; // mark as seen
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
const auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || ny < 0 || nx == n || ny == m || g[ny][nx] == '#')
continue;
if (g[ny][nx] == 'E') return steps + 1;
q.emplace(nx, ny);
g[ny][nx] = '#'; // mark as seen
}
}
++steps;
}
return -1;
}
int main() {
cin >> T;
while (T--) {
cin >> m >> n;
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x) {
cin >> g[y][x];
if (g[y][x] == 'S') sx = x, sy = y;
}
int ans = bfs(sx, sy);
cout << ( ans == -1 ? "oop!" : to_string(ans) ) << endl;
}
return 0;
}