迷宫的最短路径

题目描述：

给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。
 

输入示例：

N=10，M=10（'#'表示墙壁，'.'表示通道，'S'和'G'分别表示起点和终点）

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

 

输出示例：

22

 

题目分析：

宽度优先遍历按照距开始状态由近及远的顺序进行遍历，因此可以很容易的用来求最短路径、最少操作之类问题的答案。
 
 

用C++解决问题：

#include <iostream>
#include <utility>
#include <queue>
using namespace std;

const int INF=100000000;//迷宫中未遍历的地方
typedef pair<int,int> P;

//输入
char maze[100][101];//表示迷宫
int N,M;
int sx,sy;//起点坐标 
int gx,gy;//终点坐标

int d[100][100];//到各个位置（坐标）的最短距离的数组

//4个方向移动的向量
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

//求从起点到终点的最短距离
//如果无法到达，则是INF
int bfs(){
	queue<P> que;//创建类型为P的队列
	//把所有位置初始化为INF
	int i,j;
	for(i=0;i<N;i++){
		for(j=0;j<M;j++){
			d[i][j]=INF;
		}
	}
	
	//把起点加入队列，并把这一地点的距离设置为0 
	que.push(P(sx,sy));
	d[sx][sy]=0;
	
	//不断循环，直到队列的长度为0
	while(que.size()){
		P p=que.front();que.pop();
		//如果是终点，则结束搜索
		if(p.first==gx&&p.second==gy) break;
		
		//以该点为中心，四个方向循环
		for(i=0;i<4;i++){
			int nx=p.first+dx[i],ny=p.second+dy[i];
			
			//判断是否可以移动以及是否已经访问过 
			if(0<=nx&&nx<N&&0<=ny&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF){
				//可以移动，则加入到队列，并且该位置的距离确定为p的距离+1
				que.push(P(nx,ny));
				d[nx][ny]=d[p.first][p.second]+1; 
			}
		} 
	}
	//返回矩阵d中终点值，即为最短路径 
	return d[gx][gy];
} 

void solve(){
	int res=bfs();
	printf("最小步数为：%d\n",res);
}

int main(int argc, char** argv) {
	int i,j;
	printf("请输入迷宫的行数：\n");
	scanf("%d",&N);
	printf("请输入迷宫的列数：\n");
	scanf("%d",&M);
	
	printf("请输入迷宫的起点坐标（从0开始，中间用空格隔开）：\n");
	scanf("%d %d",&sx,&sy);
	printf("请输入迷宫的终点坐标（从0开始，中间用空格隔开）：\n");
	scanf("%d %d",&gx,&gy);
	
	printf("请输入该迷宫：\n");
	for(i=0;i<N;i++){
		for(j=0;j<M+1;j++){//多一列用来存放回车符
			scanf("%c",&maze[i][j]);
		}
	}
	
	solve();
	return 0;
}

 

代码分析：

N=10，M=10，输入迷宫为输入样例中的迷宫，起点(0,1)，终点(9,8)。
在函数bfs()中，先将矩阵d初始化，表示每一点都没有访问过。
首先将起点放入队列进行宽度遍历，以该点为中心，依次下、右、上、左遍历，符合要求的放入队列，之后取出进行宽度遍历。直到队列中没有点。
最后返回矩阵d中(gx,gy)的值即为最短路径。