问题：迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进；如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有可能的能跟都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。而且在求解迷宫路径中，所求得的路径必须是简单路径。即在求得的路径上不能有重复的同一块通道。为了表示迷宫，设置一个数组，，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块为墙，数组如下所示：
int mg[10][10] = {//定义一个迷宫，0表示通道，1表示墙{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,1,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};对于迷宫中每个方块，都有上下左右四个方块相邻，第i行第j列的当前方块的位置为(i,j)，规定上方方块为方位0，按顺时针方向递增编号。假设从方位0到方位3的方向查找下一个可走方块。 为便于回溯，对于可走的方块都要进栈，并试探它的下一个可走方位，将这个可走的方位保存到栈中，栈定义如下：
struct St//定义一个栈，保存路径{int i;//当前方块的行号int j;//当前广场的列号int di;//di是下一可走方位的方位号} St[MaxSize];//定义栈求解路径过程为：先将入口进栈（初始方位设置为-1），在栈不为空时循环：取栈顶方块（不退栈），若是出口，则输出栈中方块即为路径。否则，找下一个可走的相邻方块，若不存在这样的方块，则退栈。若存在，即将其方位保存到栈顶元素中，并将这个可走相邻方块进栈（初始方位设置为-1）。为保证试探可走相邻方块不是已走路径上的方块，如（i,j）已经进栈，在试探(i+1,j)的下一可走方块时，又试探到（i,j），这样会引起死循环，为此，在一个方块进栈后，将对应的mg数组元素值改为-1（变为不可走），当退栈时（没有可走的相邻方块），将其恢复为0.
源码：<span style="font-size:14px;">#include <iostream>#include <iomanip>#include <cstdlib>using namespace std;#define MaxSize 100int maze[10][10] = //定义一个迷宫，0表示通道，1表示墙{{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,1,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};struct Try //定义一个栈，保存路径{int i;//当前方块的行号int j;//当前广场的列号int d;//di是下一可走方位的方位号} path[MaxSize];//定义栈int top = -1;//初始化栈指针void findPath(int xb, int yb, int xe, int ye)//路径为从(xb,yb)到(xe,ye){int i, j, d, find, k;top++;//初始方块进栈path[top].i = xb;path[top].j = yb;path[top].d = -1;maze[xb][yb] = -1;while(top>-1)//栈不为空时循环{i = path[top].i;j = path[top].j;d = path[top].d;if(i==xe && j==ye)//找到了出口，输出路径{cout << "迷宫路径如下：\n";for(k=0; k<=top; k++){cout << "\t(" << path[k].i << "," << path[k].j << ")";if((k+1)%5==0) cout << endl;//每输出五个方块后换一行}cout << endl;return;}find = 0;while(d<4 && find==0)//找下一个可走的点{d++;switch(d){case 0: //向上i = path[top].i-1;j = path[top].j;break;case 1: //向右i = path[top].i;j = path[top].j+1;break;case 2: //向下i = path[top].i+1;j = path[top].j;break;case 3: //向左i = path[top].i;j = path[top].j-1;break;}if(maze[i][j]==0) find = 1;//找到通路}if(find==1)//找到了下一个可走方块{path[top].d = d;//修改原栈顶元素的d值top++;//下一个可走方块进栈path[top].i = i;path[top].j = j;path[top].d = -1;maze[i][j] = -1;//避免重复走到这个方块//cout << "\t(" << path[top].i << "," << path[top].j << ")"; //显示经过的试探}else //没有路可走，则退栈{maze[path[top].i][path[top].j] = 0;//让该位置变成其它路径可走方块top–;}}cout << "没有可走路径！\n";}int main(){findPath(1,1,8,8); //从(1,1)入，(8,8)出return 0;}</span>运行结果：
@ Mayuko
总有看腻的时候，不论何等荣华的身份，
