问题描述：
存在这样一个迷宫：
int mg[5][5]={
{0,0,0,0,0},
{0,1,0,1,0},
{0,1,1,0,0},
{0,1,1,0,1},
{0,0,0,0,0}
};
求一条从起点 (0，0) 到终点 (4，4) 的最短路，并打印出路径。
思路：
广度优先搜索，从 (0，0) 开始，将它下一步能到达的全部点标记出来，(0，1) 和 (1，0) ，然后将其状态标记为 -1，接下来对 (0，1) 和 (1，0) 做相同的操作，具体先操作哪个和你定义的行进方向有关，和深搜很相似，直到有一条路先到达终点，程序结束，先到达的那个就是最短路，因为每走一步都会试遍所有可走的路。然而路很好找，要将它打印出来，就有点问题了，我们在这里用到的数据结构是队列，手动运行一下(规定 上右下左 为判断方向的顺序)：
(0 , 0) 入队，判断之后，(0，1) 入队，(1，0)入队，(0，0) 状态标记为 -1，开始判断 (0，1)，(0，2) 入队，状态标记为 -1，开始判断 (1，0)，(2，0)入队，状态标记为 -1，开始判断 (0，2) ......
到达终点后，队列里存在一条完整的路径，但是其中也夹杂着没有走完的那一条路，这时我们需要打印出卢静，就需要我们在入队的时候加上一个标记，即前驱，对于 (2，0)，它的前驱就是 (1，0)，那么在打印的时候，我们只要根据前驱就可以打印出整条路径了。
代码实现：
#include <iostream> using namespace std; int mg[7][7]={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,1,0,1}, {1,0,1,1,0,0,1}, {1,0,1,1,0,1,1}, {1,0,0,0,0,0,1}, {1,1,1,1,1,1,1} }; typedef struct { int i,j; int pre; }Box; typedef struct { Box data[100]; int front,rear; }QuType; void print(QuType qu,int index) { if(index == -1) return; print(qu,qu.data[index].pre); cout<<"("<<qu.data[index].i<<","<<qu.data[index].j<<")"<<endl; } bool mgpath(int xi,int yi,int xe,int ye) { int i,j,find = 0,di; QuType qu; qu.front = qu.rear = -1; qu.rear++; qu.data[qu.rear].i = xi; qu.data[qu.rear].j = yi; qu.data[qu.rear].pre = -1; mg[xi][yi] = -1; while(qu.front != qu.rear && !find) { qu.front++; i = qu.data[qu.front].i; j = qu.data[qu.front].j; if(i == xe && j == ye) { find = 1; print(qu,qu.front); return true; } for(di = 0;di < 4;di++) { switch(di) { case 0: i = qu.data[qu.front].i-1; j = qu.data[qu.front].j; break; case 1: i = qu.data[qu.front].i; j = qu.data[qu.front].j+1; break; case 2: i = qu.data[qu.front].i+1; j = qu.data[qu.front].j; break; case 3: i = qu.data[qu.front].i; j = qu.data[qu.front].j-1; break; } if(mg[i][j] == 0) { qu.rear++; qu.data[qu.rear].i = i; qu.data[qu.rear].j = j; qu.data[qu.rear].pre = qu.front; mg[i][j] = -1; } } } return false; } int main() { if(!mgpath(1,1,5,5)) cout<<"no way!"; return 0; }