#include<bits/stdc++.h> using namespace std; int n,m,a1,b1; struct node{ int x;int y;int d; }; int x[4]={0,-1,0,1}; int y[4]={-1,0,1,0}; char c[500][500]; bool f[500][500]; int bfs(){ struct node l; l.x=a1; l.y=b1; l.d=0; queue<node>q; q.push(l); while(!q.empty()){ for(int i=0;i<4;++i){ int xx=q.front().x+x[i]; int yy=q.front().y+y[i]; if(xx>0&&xx<=n&&yy>0&&yy<=m&&c[xx][yy]!='#'&&f[xx][yy]==false){ f[xx][yy]=true; if(c[xx][yy]=='E') return q.front().d+1; struct node k; k.x=xx; k.y=yy; k.d=q.front().d+1; q.push(k); } } q.pop(); } return 0; } int main(){ while(scanf("%d %d\n",&n,&m)!=EOF){ memset(f,false,sizeof(f)); for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ scanf("%c",&c[i][j]); if(c[i][j]=='S') a1=i,b1=j; } getchar(); } int ans=bfs(); printf("%d\n",ans); } } |
Double click to view unformatted code.