题目：给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。
#include <iostream> #include<queue> using namespace std; const int INF=100000; int n,m,sx,sy,ex,ey; int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; int step[105][105]; char maze[105][105]; typedef pair<int,int> P; void solve(); int bfs(); int main() { while(cin>>n>>m){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>maze[i][j]; if(maze[i][j]=='S'){ sx=i;sy=j; } if(maze[i][j]=='G'){ ex=i;ey=j; } step[i][j]=INF; } } solve(); } return 0; } void solve(){ int ans=bfs(); cout<<ans<<endl; } int bfs(){ queue<P> q; q.push(P(sx,sy)); step[sx][sy]=0; while(q.size()){ P p=q.front(); if(p.first==ex&&p.second==ey) break; q.pop(); for(int i=0;i<4;i++){ int tx=p.first+dx[i],ty=p.second+dy[i]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&step[tx][ty]==INF&&maze[tx][ty]!='#'){ q.push(P(tx,ty)); step[tx][ty]=step[p.first][p.second]+1; } } } return step[ex][ey]; }