定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

Solving code:

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

struct Point{
	int x, y;
}pre[5][5];
int vis[5][5], dir[4][2] = {{0, 1},{0, -1},{1, 0},{-1, 0}}, maze[5][5];

void Print(){
	stack<Point> s;
	Point p;p.x = 4, p.y = 4;
	s.push(p);
	while(1){
		if(0 == p.x && 0 == p.y)
			break;
		p = pre[p.x][p.y];
		s.push(p);
	}
	while(!s.empty()){
		cout << '(' << s.top().x << ", " << s.top().y << ')' << endl;
		s.pop();
	}
}

void bfs(int x, int y){
	queue<Point> q;
	Point beg;beg.x = x, beg.y = y;
	q.push(beg);
	vis[x][y] = 1;
	while(!q.empty()){
		Point now = q.front();q.pop();
		if(4 == now.x && 4 == now.y){
			Print();
			return ;
		}
		for(int i = 0;i < 4;i++){
			int dx = now.x + dir[i][0];
			int dy = now.y + dir[i][1];
			if(dx >= 0 && dx <= 4 && dy >= 0 && dy <= 4 && !maze[dx][dy]){
				if(!vis[dx][dy]){
					vis[dx][dy] = 1;
					pre[dx][dy] = now;
					Point Next;Next.x = dx, Next.y = dy;
					q.push(Next);
				}
			}
		}
	}
}

int main(){
	for(int i = 0;i < 5;i++)
		for(int j = 0;j < 5;j++)
			cin >> maze[i][j];
	bfs(0, 0);
	return 0;
}

算法分析及总结：

这个题没有权重，所以直接用bfs求最短路径
bfs第一次到达终点的时候就是最短路，因为它只能从四个方向去走，所以我们设定方向数组dir[4][2]，然后当然还需要队列，队列是用来存当前节点然后便于找到它的上下左右相邻节点。所以我们知道每次更新入队的节点都是队首节点的路径+1，然后根据同一队首入队的节点路径长度相当。

难点：怎么输出最短路径？

我们可以设计一个Point类型的数组pre，设定pre[i][j] = 位置为(i, j)的上一个节点，然后我们知道最终的结果是(4, 4)，然后设置一个栈，让点(4, 4)入栈，然后根据数组pre得到(4, 4)的上一个节点，依次类推，直到最短路的路径走完，也就是到(0, 0)这个点！然后根据栈先进后出的特性，我们从栈顶输出，依次退栈，就得到顺序的路径了。