1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4  5 using namespace std; 6  7 const int INF=100000000; 8  9 typedef pair<int,int> P;10 11 char maze[200][200];12 int N,M;13 int sx,sy;14 int gx,gy;15 int d[200][200];16 int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};17 18 int bfs(){19     queue<P> que;20     for(int i=0;i<N;i++){21         for(int j=0;j<M;j++){22             d[i][j]=INF;23         }24     }25     que.push(P(sx,sy));26     d[sx][sy]=0;27 28     while(que.size()){29         P p=que.front();que.pop();30         if(p.first==gx&&p.second==gy) break;31 32         for(int i=0;i<4;i++){33             int nx=p.first+dx[i],ny=p.second+dy[i];34             if(nx>=0 && nx<N && ny>=0 &&ny<M && maze[nx][ny]!=‘#‘ && d[nx][ny]==INF){35                 que.push(P(nx,ny));36                 d[nx][ny]=d[p.first][p.second]+1;37             }38         }39     }40     return d[gx][gy];41 }42 43 void solve(){44     int res=bfs();45     printf("%d\n",res);46 }47 48 int main()49 {50     while(~scanf("%d %d",&N,&M)){51         getchar();52         for(int i=0;i<N;i++){53             for(int j=0;j<M;j++){54                 scanf("%c",&maze[i][j]);55                 if(maze[i][j]==‘S‘){56                     sx=i;57                     sy=j;58                 }59                 if(maze[i][j]==‘G‘){60                     gx=i;61                     gy=j;62                 }63             }64             getchar();65         }66         solve();67     }68     return 0;69 }