AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
wyf
,
2021-02-02 21:37:01
,
所有人可见
,
阅读 807
用宽搜统计步数:每次从起点开始向四周扩展,如果可扩展,即里面是’.’,并且不能越界,用距离数组统计每个点距离起点得距离,第一次扩展到终点则是最短步数,即用时最少
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=210;
char g[N][N];
int dist[N][N];
int n,m;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
bool bfs(int x,int y){
queue<PII> q;
memset(dist,0,sizeof dist);
q.push({x,y});
g[x][y]='#';
while(q.size()){
PII t=q.front();
q.pop();
int x=t.first,y=t.second;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if((g[xx][yy]=='.'||g[xx][yy]=='E')&&xx<n&&xx>=0&&yy<m&&yy>=0){
if(g[xx][yy]=='E'){
dist[xx][yy]=dist[x][y]+1;
return true;
}
g[xx][yy]='#';
dist[xx][yy]=dist[x][y]+1;
q.push({xx,yy});
}
}
}
return false;
}
int main(){
int t;
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];
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j]=='S'){
if(bfs(i,j)){
for(int x=0;x<n;x++)
for(int y=0;y<m;y++)
if(g[x][y]=='E')cout<<dist[x][y]<<endl;
}
else cout<<"oop!"<<endl;
}
}
return 0;
}