AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
muchun
,
2024-04-08 14:37:05
,
所有人可见
,
阅读 1
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=210;
int t,r,c;
PII s[N];
char a[N][N];
int dist[N][N];
void dfs(PII start)
{
queue<PII> q;
q.push(start);
while(!q.empty())
{
PII t=q.front();
q.pop();
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
for(int i=0;i<4;++i)
{
int x0=t.x + dx[i];
int y0=t.y + dy[i];
if(a[x0][y0]=='#')continue;
if(a[x0][y0]=='.')
{
dist[x0][y0]=dist[t.x][t.y]+1;
q.push({x0,y0});
a[x0][y0]='#';
}
if(a[x0][y0]=='E')
{
cout << dist[t.x][t.y]+1<< endl;
return;
}
}
}
cout << "oop!"<< endl;
return ;
}
int main(){
cin >> t;
while(t--)
{
PII start;
memset(a,'#',sizeof(a));
memset(dist,0,sizeof(dist));
cin >> r >>c ;
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
{
cin >> a[i][j];
if(a[i][j]=='S')
{start.x=i;
start.y=j;
}
}
dfs(start);
}
return 0;
}