迷宫最短路径(bfs)

给定一个大小为N*M的迷宫，由通道('.')和墙壁('#')组成，其中通道S表示起点，通道G表示终点，每一步移动可以达到上下左右中不是墙壁的位置。试求出起点到终点的最小步数。（本题假定迷宫是有解的）

(N,M<=100)

样例输入：

10 10

#	S	#	#	#	#	#	#	.	#
.	.	.	.	.	.	#	.	.	#
.	#	.	#	#	.	#	#	.	#
.	#	.	.	.	.	.	.	.	.
#	#	.	#	#	.	#	#	#	#
.	.	.	.	#	.	.	.	.	#
.	#	#	#	#	#	#	#	.	#
.	.	.	.	#	.	.	.	.	.
.	#	#	#	#	.	#	#	#	.
.	.	.	.	#	.	.	.	G	#

样例输出：

22

来自《挑战程序设计竞赛（第2版）》

该题很好地体现了BFS是如何与队列先进先出(FIFO)的思想联系起来的。搜索时先将初始状态添加到队列里，此后从队列的最前端不断取出状态，把从该状态可以转移到的状态中尚未访问过的部分加入队列，如此往复，直到队列被取空或找到了问题的解。总是先搜索距离初始状态近的状态，按照距开始状态由近及远的顺序进行搜索。对于同一个状态只经过1次，复杂度为O(状态数X转移的方式)

对本题，转移的方式为四方向移动，状态数等于迷宫的大小，复杂度为O(4xNxM)=O(NxM)

代码如下:

#include <iostream>  
#include <queue>  
using namespace std;  
const int MAX_N = 100;  
const int MAX_M = 100;  
const int INF = 0x3f3f3f3f;  
typedef pair<int, int> P;  
char maze[MAX_N][MAX_M + 1];  
int N, M;  
int sx, sy; //起点的位置  
int gx, gy; //终点的位置  

int d[MAX_N][MAX_M];//储存起点到某一点的距离  
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; //表明每次x和y方向的位移  

void bfs()  
{  
    queue<P> que;  
    for (int i = 0; i < N; i++)  
        for (int j = 0; j < M; j++)  
            d[i][j] = INF;  //初始化所有点的距离为INF  
    que.push(P(sx, sy));  
    d[sx][sy] = 0;  //从起点出发将距离设为0，并放入队列首端  

    while (que.size()) //题目保证有路到终点，所以不用担心死循环  
    {  
        P p = que.front(); que.pop();//弹出队首元素  
        int i;  
        for (i = 0; i < 4; i++)  
        {  
            int nx = p.first + dx[i];  
            int ny = p.second + dy[i];//移动后的坐标  
            //判断可移动且没到过  
            if (0 <= nx&&nx < N  
                && 0 <= ny&&ny < M  
                &&maze[nx][ny] != '#'  
                &&d[nx][ny] == INF)//之前到过的话不用考虑，因为距离在队列中递增，肯定不会获得更好的解  
            {  
                que.push(P(nx, ny));    //可以移动则设定距离为之前加一，放入队列  
                d[nx][ny] = d[p.first][p.second] + 1;  
                if(nx==gx && ny==gy) break;  

                        }  
        }  
        if(i!=4) break;  
    }  

}  

int main()  
{  
    cin>>N>>M;  
    for (int i = 0; i < N; i++)  
        cin>>maze[i];  
    for (int i = 0; i < N; i++)  
        for (int j = 0; j < M; j++)  
        {  
            if (maze[i][j] == 'S')  
            {  
                sx = i; sy = j;  
            }  
            if (maze[i][j] == 'G')  
            {  
                gx = i; gy = j;  
            }  
        }  
    bfs();  
    cout<<d[gx][gy]<<endl;  

    return 0;  
}