题目描述：
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一格是可以走的路。
本题含有多组数据。
输入描述：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述：
左上角到右下角的最短路径，格式如样例所示。
示例：
输入：
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出：
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
解题思路：
回溯法解迷宫问题，构建结构体list存放x和y，以及next指针存储路径；push函数即前进，让路径加入新位置，pop函数即后退，将路径弹出一个位置，chkExit函数判断是否到达终点。
利用两维数组a存放迷宫图，设置（0,0）为起点开始出发，path为路径，因为迷宫没有围墙，所以要判断边界，前进则通过分析上下左右是否有可行路径决定，如果走到某个点没有可行路径了，就后退，直到到达某个点有另一条分支可行，注意该过程path一直放入弹出位置信息，确保存放的位置是最终到达终点的路径；因为path存放顺序倒序，我将其整理成string格式放入vector中，再逆序输出vector，完成路径输出。
测试代码：
#include <iostream> #include <vector> using namespace std; // 构建结构体 struct list { int x, y; struct list *next; }; typedef struct list node; typedef node* link; link push(link path, int x, int y); link pop(link path, int *x, int *y); int chkExit(int x, int y, int ex, int ey); // 路径加入新点 link push(link path, int x, int y) { link newnode; newnode = new node; if (!newnode) { cout << "Error:内存分配失败！" << endl; return NULL; } newnode->x = x; newnode->y = y; newnode->next = path; path = newnode; return path; } // 路径弹出不通的点 link pop(link path, int *x, int *y) { link top; if (path != NULL) { link temp=path; path = path->next; *x = path->x; *y = path->y; delete temp; return path; } return path; } // 到达终点 int chkExit(int x, int y, int ex, int ey) { if ((x == ex) && (y == ey)) { return 1; } return 0; } int main() { int row,col; while(cin>>row>>col) { int**a=new int *[row]; for(int i=0;i<row;++i) { a[i]=new int[col]; } for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { cin>>a[i][j]; } } link path = NULL; int x=0,y=0; path=push(path,x,y); while (x<row &&y<col) { a[x][y]=2; // 往上走 if(x-1>=0) { if(a[x-1][y]==0) { x-=1; path=push(path,x,y); continue; } } // 往下走 if(x+1<row) { if(a[x+1][y]==0) { x+=1; path=push(path,x,y); continue; } } // 往左走 if(y-1>=0) { if(a[x][y-1]==0) { y-=1; path=push(path,x,y); continue; } } // 往右走 if(y+1<col) { if(a[x][y+1]==0) { y+=1; path=push(path,x,y); continue; } } // 判断是否到达终点 if(chkExit(x, y, row-1, col-1) == 1) { break; } // 倒退 path=pop(path,&x,&y); } vector<string> result; while(path!=NULL) { string p="("+to_string (path->x)+","+to_string (path->y)+")"; result.push_back(p); path=path->next; } for(int i=result.size()-1;i>=0;--i) { cout<<result[i]<<endl; } } return 0; }
