#include<bits/stdc++.h> using namespace std; const int N = 510; int n,m; int ex,ey; char g[N][N]; typedef pair<int,int> PII; int f[N][N]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; bool have_k; void bfs(int a,int b) { queue<PII> q; q.push({a,b}); f[a][b]=0; g[a][b]='D';//将起始位置设为D,后续可能会经过 while(!q.empty()) { PII start=q.front(); q.pop(); int xx=start.first,yy=start.second; for(int i=0;i<4;i++) { int x=xx+dx[i],y=yy+dy[i]; if(x >= 1 && x <= n && y >= 1 && y <= m)//范围之内 { if(!have_k)//如果没有钥匙 { if(g[x][y]=='K')//如果找到钥匙 { g[x][y]='W';//设为w防止循环 f[x][y]=f[xx][yy]+1; have_k=true;//找到钥匙 q.push({x,y}); } else if(g[x][y]=='.'){//如果是.那么更新为D,因为有K之后就可以过D了 g[x][y]='D'; f[x][y]=f[xx][yy]+1; q.push({x,y}); } } else//如果有钥匙了 { if(g[x][y]=='D'||g[x][y]=='.')//既可以过D又可以过. { g[x][y]='W';//设置为W防止循环 f[x][y]=f[xx][yy]+1; q.push({x,y}); } } } } } if(f[ex][ey]!=0)cout<<f[ex][ey];//打印终点的步数 else cout<<"-1"; } int main() { cin>>n>>m; getchar(); int x,y; for(int i=1;i<=n;i++) scanf("%s",g[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(g[i][j]=='S') x=i,y=j;//查询起点 if(g[i][j]=='E') ex=i,ey=j;//查询终点 } bfs(x,y);//BFs起点 }
全部评论
(0) 回帖