最短路径(BFS)

宽度优先搜索

*图片来源：挑战程序设计竞赛（第2版）

题目

（

http://m.blog.csdn.net/article/details?id=50768661。

）

#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 };  //移动方向
 
void bfs()
{
	queue<P> que;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			d[i][j] = INF;	     //将所有的点置空
	que.push(P(sx, sy));  //输入起点
	d[sx][sy] = 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)
		/*如果这个点（那四个点之一）
		1.在这个地图内
		2.这个点不是‘#’（不是墙）
		3.其值等于无穷大（未被访问过）
		*/
			{
				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;
}