AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
kooo.
,
2024-04-09 23:33:23
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 210;
typedef pair<int, int> PII;
int n,m;//行 列
int k;
int dis[N][N];
int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1};
char g[N][N];
int bfs(PII start,PII end)
{
queue<PII> q;
memset(dis, -1, sizeof dis); // 把距离数组都初始化成-1
dis[start.x][start.y]=0;
q.push(start);
while(!q.empty())
{
auto t = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=t.x+dx[i];
int yy=t.y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=m)continue;
if(g[xx][yy]=='#')continue;
if(dis[xx][yy]!=-1)continue;
dis[xx][yy] = dis[t.x][t.y] + 1;
if(g[xx][yy]==g[end.x][end.y])return dis[xx][yy] ;
q.push({xx,yy});
}
}
return -1;
}
int main()
{
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",&g[i]);
}
PII start,end;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(g[i][j]=='S')
{
start={i,j};
}
if(g[i][j]=='E')
{
end={i,j};
}
}
}
int d1= bfs(start,end);
if(d1==-1)
{
cout<<"oop!"<<endl;
}
else
{
cout<<d1<<endl;
}
}
return 0;
}