【数据结构】c语言基于堆栈实现回溯法自动走迷宫( 二 ) _迷宫

< 100; i++) {for (int j = 0; j < 100; j++) {c[i][j] = 0;}}c[start_x][start_y] = 1;}//判断是否胜利，如果当前位置就是终点的话就是胜利，返回1 ，否则返回0int victory(Elemtype a[100][100], int b[3]) {if (a[b[0]][b[1]] == '$') {return 1;}else {return 0;}}//判断是否死亡，如果回到了原点就代表死亡//start_x代表开始的x坐标， start_y代表开始的y坐标//死亡返回0 ，未死亡返回1int die(int start_x, int start_y, int b[3]) {if (b[0] == start_x && b[1] == start_y) {//回到了原点代表死亡return 0;}else {return 1;}}//运行主程序，决定下一步该怎么走/*右 x,y+1上 x-1,y左 x,y-1下 x+1,y*///数组c用来记录每个格子都过的次数void run(Elemtype a[100][100],int c[100][100],int b[3],st s) {//往右边检查,如果可以走并且没有走过的话就可以走//可以走的话就要把当前位置入栈，然后走，刷新地图if ((a[b[0]][b[1] + 1] == 'e'|| a[b[0]][b[1] + 1] == '$' )&& c[b[0]][b[1] + 1] == 0) {int d[3] = {b[0],b[1]+1,1};push(s, b);for (int i = 0; i < 3; i++) {b[i] = d[i];}c[d[0]][d[1]]++;system("cls");print(a, 9, 9, b[0], b[1]);test(s);return;}//往上边检查if ((a[b[0] - 1][b[1]] == 'e'|| a[b[0] - 1][b[1]] == '$')&&c[b[0] - 1][b[1]] == 0) {int d[3] = {b[0]-1,b[1],1};push(s, b);for (int i = 0; i < 3; i++) {b[i] = d[i];}c[d[0]][d[1]]++;system("cls");print(a, 9, 9, b[0], b[1]);test(s);return;}//往左边检查if ((a[b[0]][b[1]-1] == 'e'|| a[b[0]][b[1] - 1] == '$')&&c[b[0]][b[1]-1] == 0) {int d[3] = { b[0],b[1]-1,1 };push(s, b);for (int i = 0; i < 3; i++) {b[i] = d[i];}c[d[0]][d[1]]++;system("cls");print(a, 9, 9, b[0], b[1]);test(s);return;}//往下边检查if ((a[b[0]+1][b[1]] == 'e'|| a[b[0] + 1][b[1]] == '$')&&c[b[0] + 1][b[1]] == 0) {int d[3] = { b[0] + 1,b[1],1 };push(s, b);for (int i = 0; i < 3; i++) {b[i] = d[i];}c[d[0]][d[1]]++;system("cls");print(a, 9, 9, b[0], b[1]);test(s);return;}//走到这里就说明没有路可以走了，这时候要回溯//从堆栈里退栈然后继续这一步pop(s, b);//b里储存的就是栈顶的位置c[b[0]][b[1]]++;//退栈之后那一格的步数加一system("cls");print(a, 9, 9, b[0], b[1]);test(s);}int main(){int count = 0;//记录走过的步数char a[100][100];draw(a);st s = (Stack *)malloc(sizeof(Stack));init_s(s);int b[3] = { 1,1,1 };//从1,1开始，并且在这个格子呆过一个回合int c[100][100];//记录步数的数组init_c(c, 1, 1);run(a, c, b, s);cout << "当前步数为：" << ++count << endl;Sleep(500);//system("pause");while (victory(a, b) == 0) {if (die(1, 1, b) == 0) {cout << "又回到最初的起点，这是个走不出去的迷宫~" << endl;return 0;}Sleep(500);//system("pause");run(a, c, b, s);cout << "当前步数为：" << ++count << endl;}//出来就说明获得了胜利cout << "成功走出了迷宫！！" << endl;return 0;}

文章插图
基本思路就是以一定的顺序检查上下左右格子是否可以走，如果可以走的话，就把之前的一步压入堆栈中，当遇到无路可走的情况的时候，就退栈然后继续检查有没有可以走的路，知道走出迷宫为止，如果没有可以走出迷宫的路的话，栈会被弹空然后没有可以走的路了。最后调试的结果如下：

文章插图