最普通bfs--AcWing 1101. 献给阿尔吉侬的花束
作者:
古德古德
,
2022-04-07 20:51:00
,
所有人可见
,
阅读 184
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int t;
int n,m;
const int N = 210;
char gr[N][N];
PII st,ed;
int dist[N][N];
int dx[4]= {-1,0,1,0}, dy[4]= {0,1,0,-1};
void bfs()
{
memset(dist,-1,sizeof dist);
queue<PII> q;
q.push({st.x,st.y});
dist[st.x][st.y] = 0;
while(q.size())
{
PII t = q.front(); q.pop();
for(int i = 0 ; i< 4 ;i++)
{
int a = dx[i] + t.x , b = dy[i] + t.y;
if(a<0 || a >=n || b<0 || b>=m) continue; //易错点 把m写成n
if(gr[a][b] == '#') continue; //易错点 没有写
if(dist[a][b] != -1) continue;
dist[a][b] = dist[t.x][t.y] +1;
q.push({a,b});
}
}
}
int main()
{
cin >> t;
while(t--)
{
cin >> n>> m;
for(int i=0 ; i< n ; i++)
for(int j=0; j < m; j++)
{
cin >> gr[i][j];
if(gr[i][j] == 'S') st = {i,j};
if(gr[i][j] == 'E') ed = {i,j};
}
bfs();
if(dist[ed.x][ed.y] != -1) cout << dist[ed.x][ed.y] << endl;
else cout << "oop!" <<endl;
}
return 0;
}