迷宫的最短路径【BFS】

迷宫的最短路径 时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述:
给定一个大小为N * M 的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点 。
限制条件： N ， M<=100 。（ # . S G 分别代表 墙壁、通道、起点和终点。）

输入:
第1行：两个空格分隔的整数:n和m
输出入n行m列的迷宫图

输出:
输出一个整数，表示从起点到终点所需的最小步数。

样例输入:
10 10

样例输出:
22

刚刚完成深度优先搜索的学习，理解记住两个经典例子部分和问题 与 Lake Counting基本上便能理解DFS了。
之后，又学习了广度优先搜索【BFS】，起初自己写的时候，利用四个分开的循环分别递归，虽然最后也出结果了，但是看完《程序设计竞赛》里面的答案才知道自己是多笨。。。。hhhhh
俺还有电子版哦，需要的可私，或者评论留邮件。。。emmm

宽度优先搜索按照距开始状态由近及远的顾序进行搜索，因此可以很容易地用来求最短路径。最少操作之类问题的答案。这个问题中，状态仅仅是目前所在位置的坐标.因此可以构造成pair.或者编码成int来表达决态。当状态更加复杂时，就需要村装成一个类来表示状态了。 转移的方式为四方向移动，状态数与迷宫的大小是相等的。

宽度优先搜索中.只要将已经访问过的状态用标记管理起来。就可以很好地做到由近及远的搜索。这个问题中由于要求最短距离，不妨用 d [ i ] [ j ] 数组把最短距离保存起来。初始时用充分大的常数INF来初始化它，这样尚未到达的位置就是INF，也就同时起到了标记的作用。

虽然到达终点时就会停止搜索，可如果继续下夫直到队列为空的话，就可以计算出到各个位冒的最短距离。此外，如果搜索到最后. 依然为INF的话,便可得知这个位置就是无法从起点到达的位置

在今后的程序中，使用像INF这样充分大的常数的情况还很多。不把INF当作例外，而是直接参与普通运算的情况也很常见。这种情况下，如果INF过大就可能带来溢出的危险。

#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std; 
typedef pair<int , int> p;
const int INF=99666; 
char map[1000][1000];
int d[1000][1000];         //标记数组 
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int n,m,sx,sy,gx,gy;
int 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 q=que.front();
		que.pop();
		if(q.first==gx&&q.second==gy)break;
		//四个方向
		for(int i=0;i<n;i++)
		{
			int nx=q.first+dx[i];
			int ny=q.second+dy[i];
			//条件判断，是否可以进行宽度优先搜索;
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&map[nx][ny]!='#'&&d[nx][ny]==INF)
			{
				que.push(p(nx,ny));
				d[nx][ny]=d[q.first][q.second]+1;
			} 
		}	 
	}
	return d[gx][gy];
}
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			cin >> map[i][j];  
			if(map[i][j]=='S'){sx=i;sy=j;}
			if(map[i][j]=='G'){gx=i;gy=j;}
		} 
	int s=bfs();	
	cout << s << endl;
		for(int i=0;i<n;i++,cout << endl)
		for(int j=0;j<m;j++)
		{
			if(d[i][j]!=INF)printf("%3d",d[i][j]);
			else printf("   ");
		} 
	return 0;
}

宽度优先搜索与深度优先搜索一样,都会生成所有能够遍历到的状态,因此需要对所有状态进行处理时使用宽度优先搜索也是可以的。但是递归函数可以很简短地编写,而且状态的管理也更简单，所以大多数情况下还是用深度优先搜索实现。反之，在求取最短路时深度优先搜索需要反复经过同样的状态，所以此时还是使用宽度优先搜索为好。

宽度优先搜索会把状态逐个加入队列，因此通常需要与状态数成正比的内存空间。反之，探度优先搜索是与最大的递归深度成正比的。-般与状态数相比，递归的深度并不会太大，所以可以认为深度优先搜索更加节省内存。

改革尚未成功，同志仍需努力！！！