题目：
迷宫问题
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 31544 | Accepted: 18065 |
Description
定义一个二维数组：
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 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
思路：
//用队列来广搜，然后走过的地方标记下并沿路建并查集，然后用并查集回溯并把点放到栈里，最后pop栈输出结果
代码：
#include#include #include using namespace std;int graph[7][7];//存图bool marked[7][7];//标记走过的点struct pos{ int x; int y;};queue q;pos un[7][7];//并查集,用于找回路stack s;//用于回路逆序输出void init()//初始化{ pos t; for(int i = 0; i < 7; i++) { for(int j = 0; j < 7; j++) { t.x = i; t.y = j; un[i][j] = t; graph[i][j] = 1;//图周围放一圈墙 marked[i][j] = false; } }}void bfs()//广搜{ //创建起始点 pos p; p.x = p.y = 1; q.push(p); marked[1][1] = true; //搜索所有点 while(!q.empty()) { pos c = q.front(); q.pop(); pos t = c; t.x++; //搜索当前点周围的可走点并放入队列中 if(graph[t.x][t.y]==0 && !marked[t.x][t.y]) { q.push(t); marked[t.x][t.y]=true; un[t.x][t.y] = c; } t.x-=2; if(graph[t.x][t.y]==0 && !marked[t.x][t.y]) { q.push(t); marked[t.x][t.y]=true; un[t.x][t.y] = c; } t.x++; t.y++; if(graph[t.x][t.y]==0 && !marked[t.x][t.y]) { q.push(t); marked[t.x][t.y]=true; un[t.x][t.y] = c; } t.y-=2; if(graph[t.x][t.y]==0 && !marked[t.x][t.y]) { q.push(t); marked[t.x][t.y]=true; un[t.x][t.y] = c; } }}int main(){ //初始化 init(); //输入 for(int i = 1; i <= 5; i++) { for(int j = 1; j <= 5; j++) cin >> graph[i][j]; } bfs(); pos t; t.x = t.y = 5; //利用并查集从终点回溯，并把点放入栈中 while(t.x != un[t.x][t.y].x || t.y != un[t.x][t.y].y) { s.push(t); t = un[t.x][t.y]; } t.x = t.y = 1; s.push(t); //pop栈，输出结果 while(!s.empty()) { t = s.top(); s.pop(); printf("(%d, %d)\n",t.x-1,t.y-1); } return 0;}