迷宫问题的代码交换
我不用栈解决了迷宫的多条路经的输出代码如下:
程序代码:
#include <stdio.h> #include <stdlib.h> void visit(int, int); int maze[9][9] = {{1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 1, 1, 0, 1, 1, 0, 1}, {1, 0, 1, 0, 0, 1, 0, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 0, 1, 0, 1}, {1, 1, 0, 1, 1, 0, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}}; int startI = 1, startJ = 1; // 入口 int endI = 7, endJ = 7; // 出口 int main(void) { int i, j; printf("显示迷宫:\n"); for(i = 0; i < 9; i++) { for(j = 0; j < 9; j++) if(maze[i][j] == 1) printf("█"); else printf(" "); printf("\n"); } visit(startI, startJ); return 0; } void visit(int i, int j) { int m, n; maze[i][j] = 2; //标记 if(i == endI && j == endJ) { printf("\n显示路径:\n"); for(m = 0; m < 9; m++) { for(n = 0; n < 9; n++) if(maze[m][n] == 1) printf("█"); else if(maze[m][n] == 2) printf("◇"); else printf(" "); printf("\n"); } } if(maze[i][j+1] == 0) visit(i, j+1);//右 if(maze[i+1][j] == 0) visit(i+1, j);//下 if(maze[i][j-1] == 0) visit(i, j-1);//左 if(maze[i-1][j] == 0) visit(i-1, j);//上 maze[i][j] = 0;//把标记还原 }
但我们数据结构课程设计要求用栈,求用栈解决
要求如下:
迷宫问题
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
基本要求:
(1)实现一个栈类型,然后编写一个求解迷宫的程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。
(2)求得迷宫中所有可能的通路;
(3)以方阵形式输出迷宫及其通路。(选做)
测试数据:
迷宫的测试数据如下:左上角(1,1)为入口,右下角(9,8)为出口。
1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
实现提示:
计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。
可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(m,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫中任一位置,均可约定有东、南、西、北四个方向可通。
求代码