AcWing 1101. 献给阿尔吉侬的花束(BFS)
原题链接
简单
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2e2 + 10;
int t, n, m, sx, sy;
char g[N][N];
bool st[N][N];
int dir[5] = {0, 1, 0, -1, 0};
void bfs(const int& sx, const int& sy, char g[][N])
{
memset(st, false, sizeof st);
queue<pair<pair<int, int>, int>> q;
q.push({{sx, sy}, 0});
st[sx][sy] = true;
while (q.size())
{
int x = q.front().first.first;
int y = q.front().first.second;
int step = q.front().second;
if (g[x][y] == 'E')
{
cout << step << endl;
return;
}
for (int i = 0; i < 4; ++ i)
{
int tx = x + dir[i];
int ty = y + dir[i + 1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && !st[tx][ty] && g[tx][ty] != '#')
{
st[tx][ty] = true;
q.push({{tx, ty}, step + 1});
}
}
q.pop();
}
cout << "oop!" << endl;
}
int main()
{
cin >> t;
while (t --)
{
cin >> n >> m;
for (int i = 0; i < n; ++ i)
{
for (int j = 0; j < m; ++ j)
{
cin >> g[i][j];
if (g[i][j] == 'S') sx = i, sy = j;
}
}
bfs(sx, sy, g);
}
return 0;
}