#include<stdlib.h> #include<math.h> #include<stdio.h> #define N 105 #define min(x,y) (x<y?x:y) char map[N][N]; int vis[N][N]; int n,m,minz=999999; int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int check(int x,int y) { if((x>=0&&x<n)&&(y>=0&&y<m)) return 1; return 0; } int DFS(int x,int y,int dp) { int i,j; if(map[x][y]=='E') { minz=min(minz,dp); return 1; } for(i=0;i<4;i++) { int tmpx,tmpy; tmpx=x+step[i][0]; tmpy=y+step[i][1]; if(map[tmpx][tmpy]=='#') continue; if(check(x,y)==1&&vis[tmpx][tmpy]==0) { vis[tmpx][tmpy]=1; DFS(tmpx,tmpy,dp+1); vis[tmpx][tmpy]=0; } } return 0; } int main() { int x,y,i,j; while(scanf("%d%d",&n,&m)!=EOF) { x=y=minz=999999; for(i=0;i<n;i++) scanf("%s",map[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) vis[i][j]=0; for(i=0;i<n;i++) { if(x!=minz&&y!=minz) break; for(j=0;j<m;j++) { if(map[i][j]=='S') { x=i,y=j; break; } } } DFS(x,y,0); if(minz==999999) printf("%d\n",0); else printf("%d\n",minz); } return 0; } |
Double click to view unformatted code.