数据结构迷宫的求解

从迷宫从入口到出口的路径求解是个经典问题，本文章采用《数据结构 C语言版》上的“穷举求解的方法”，即从入口处发，顺某一方向向前探索，若能走通，则继续往前走，否则原路返回，换一个方向继续探索，直到所有的通路都探索完为止。为了保证每个位置都可以原路退回，所以采取后进先出出的栈来储存当前位置。

       在本文章中我才用0代表可通过的路，1代表墙壁，-1代表该路段已走过，迷宫如下图所示： 

 迷宫中一条路径的基本思想为：若当前位置可以通向下一个位置，则将该位置信息（坐标，方向）入栈，并向下一位置移动，如此重复上述过程，直到找到出口位置，如果当前位置无法通向下一个位置，则实行出栈操作，返回上一个位置进行探索。

算法具体代码如下，向右行动dir=1，向下行动dir=2，向左行动dir=3，向上行动dir=4。若有出路则返回1,若无出路则返回0。

int FindWay(node* s, int a[][100], int w, int  h, int  x1, int y1, int x2, int y2, int x, int y)//(x1,y1)为起点坐标，(x2,y2)为终点坐标
{node* p;int dir;// = 1;push(s, 1, 0, 1);while ((x != x2 || y != y2) && (x != x1 || y != y1))//当前位置不在起点和终点时{if (a[x][y + 1] == 0) {a[x][y] = -1;dir = 1;push(s, x, y, dir); y++;}else if (a[x + 1][y] == 0) {a[x][y] = -1;dir = 2;push(s, x, y, dir); x++;}else if (a[x][y - 1] == 0) {a[x][y] = -1;dir = 3;push(s, x, y, dir); y--;}else if (a[x - 1][y] == 0) {a[x][y] = -1;dir = 4;push(s, x, y, dir); x--;}else{a[x][y] = -1;p = output(s);if (p) {x = p->data.x;y = p->data.y;dir = p->data.dir;free(p);}}}if (x == x2 && y == y2) {push(s, x, y, 0);return 1;}return 0;}

输出结果展示：（该结果不是上述图片中的迷宫结果，因为每次迷宫生成是随机的）

 下面附上生成迷宫的代码：

void creatmap(int a[][100], int x, int y) {int k;srand(time(0));for (int i = 0; i < x; i++) {for (int j = 0; j < y; j++) {if (i == 0 || i == x - 1) {a[i][j] = 1;}if (j == 0 || j == y - 1) {a[i][j] = 1;}else if ((i != 0 && i != x - 1) && (j != 0 && j != y - 1)) {a[i][j] = 0;}}}for (int i = 1; i < x - 1; i++) {for (int j = 1; j < y - 1; j++) {if (j < y / 3) {//规范随机数个数产生数量k = rand() % (y - 1);a[i][k] = 1;}}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！