c语言数据结构 迷宫问题 当进行退栈的时候 会不受控制地全部退栈 主要问题在 寻路方法里面
程序代码：#include<stdlib.h>
#include<math.h>
#include<stdio.h>
#include<time.h>
#define M 8
#define N 8
#define PathNum 47
#define PATH 0
#define WALL 1
#define ENTH 3
#define EXIT 4
#define FAKE 5
#define FOOT 6
typedef int ElemType;
typedef struct box {
ElemType i, j, di = 4;
} box;
typedef struct SqStick {
box data[PathNum];
ElemType top = 0;
} SqStick;
void InItzame(ElemType zame[M + 2][N + 2]);
void PrintZame(ElemType zame[M + 2][N + 2]);
void SetZame(ElemType zame[M + 2][N + 2]);
void Push( SqStick *s, ElemType zame[M + 2][N + 2], ElemType k, ElemType h);
void Pop(SqStick *s, ElemType zame[M + 2][N + 2]);
int FindEnthi(ElemType zame[M + 2][N + 2]);
int FindEnthj(ElemType zame[M + 2][N + 2]);
void SearchRoad(SqStick *s, ElemType zame[M + 2][N + 2]);
int main() {
box bo;
SqStick sq;
srand(time(NULL));
int zame[M + 2][N + 2];
InItzame(zame);
SetZame(zame);
PrintZame(zame);
SearchRoad(&sq, zame);
PrintZame(zame);
return 0;
}
//初始化迷宫
void InItzame(int zame[M + 2][N + 2]) {
for (int i = 0; i < M + 2; i++) {
for (int j = 0; j < N + 2; j++) {
zame[i][j] = 1;
}
}
}
//打印迷宫样式
void PrintZame(int zame[M + 2][N + 2]) {
for (int i = 0; i < M + 2; i++) {
for (int j = 0; j < N + 2; j++) {
switch (zame[i][j]) {
case WALL:
printf("围");
break;
case PATH:
printf(" ");
break;
case ENTH:
printf("囚");
break;
case EXIT:
printf("口");
break;
case FAKE:
printf("//");
break;
case FOOT:
printf("Ｏ");
break;
default:
break;
}
}
printf("\n");
}
}
//随机生成迷宫的通道、入口、出口
void SetZame(int zame[M + 2][N + 2]) {
int n, m;
for (int i = 0; i < PathNum; i++) {
n = rand() % 8 + 1;
m = rand() % 8 + 1;
if (zame[n][m] == PATH)
i--;
else
zame[n][m] = PATH;
}
n = rand() % 8 + 1;
m = rand() % 8 + 1;
zame[n][m] = ENTH;
while (1) {
n = rand() % 8 + 1;
m = rand() % 8 + 1;
if (zame[n][m] != ENTH)
break;
}
zame[n][m] = EXIT;
}
//获取入口下标i
int FindEnthi(int zame[M + 2][N + 2]) {
int n;
for (int i = 1; i < M + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (zame[i][j] == ENTH) {
n = i;
break;
}
}
}
return n;
}
//获取入口下标j
int FindEnthj(int zame[M + 2][N + 2]) {
int n;
for (int i = 1; i < M + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (zame[i][j] == ENTH) {
n = j;
break;
}
}
}
return n;
}
//入栈
void Push( SqStick *s, ElemType zame[M + 2][N + 2], ElemType k, ElemType h) {
s->data[s->top].i = k;
s->data[s->top].j = h;
if (zame[k][h] == PATH )
zame[k][h] = FOOT;
s->top++;
}
//出栈
void Pop(SqStick *s, int zame[M + 2][N + 2], int *f) {
if (s->top - 1 == 0) {
*f = 0;
s->top--;
} else {
zame[s->data[s->top - 1].i][s->data[s->top - 1].j] = FAKE; //出栈时将当前位置的值修改为Fake
s->top--;
}
}
//寻路
void SearchRoad(SqStick *s, int zame[M + 2][N + 2]) {
int i, j, find = 1;
i = FindEnthi( zame);
j = FindEnthj(zame);
Push(s, zame, i, j);//将入口进栈
while (find) {
if (zame[i - 1][j] == EXIT || zame[i][j + 1] == EXIT || zame[i + 1][j] == EXIT || zame[i][j - 1] == EXIT) { //检查入口位置的四周是否存在出口
break;
}
switch (s->data[s->top - 1].di) {//case 为4时向上试探，为3时向右试探，为2时向下试探，为1时向左试探（s->data[s->top-1].di默认为4）
case 4: {
if (zame[i - 1][j] == PATH) { //上一个元素是否为通路，是就入栈
i--;
s->data[s->top - 1].di--;
Push(s, zame, i, j);
if (zame[i - 1][j] == EXIT || zame[i][j + 1] == EXIT || zame[i + 1][j] == EXIT || zame[i][j - 1] == EXIT) //检查当前位置的四周是否存在出口
find = 0;
//printf("上\n");
} else {//向上试探不是通路时，将考虑向下
s->data[s->top - 1].di--;
}
}
break;
case 3: {
if (zame[i][j + 1] == PATH) { //右边的元素是否为通路，是就入栈
j++;
s->data[s->top - 1].di--;
Push(s, zame, i, j);
if (zame[i - 1][j] == EXIT || zame[i][j + 1] == EXIT || zame[i + 1][j] == EXIT || zame[i][j - 1] == EXIT) //检查当前位置的四周是否存在出口
find = 0;
//printf("右\n");
} else {
s->data[s->top - 1].di--;
}
}
break;
case 2: {
if (zame[i + 1][j] == PATH) {
i++;
s->data[s->top - 1].di--;
Push(s, zame, i, j);
if (zame[i - 1][j] == EXIT || zame[i][j + 1] == EXIT || zame[i + 1][j] == EXIT || zame[i][j - 1] == EXIT) //检查当前位置的四周是否存在出口
find = 0;
//printf("下\n");
} else {
s->data[s->top - 1].di--;
}
}
break;
case 1: {
if (zame[i][j - 1] == PATH) {
j--;
s->data[s->top - 1].di--;
Push(s, zame, i, j);
if (zame[i - 1][j] == EXIT || zame[i][j + 1] == EXIT || zame[i + 1][j] == EXIT || zame[i][j - 1] == EXIT) //检查当前位置的四周是否存在出口
find = 0;
//printf("左\n");
} else {
s->data[s->top - 1].di--;
}
}
break;
case 0: {
Pop(s, zame, &find);
printf("s->top（-1）:%d di:%d", s->top - 1, s->data[s->top - 1].di); //调试用，查看栈顶 以及栈顶di情况
printf("返\n");
}
break;
}
}
}[此贴子已经被作者于2022-4-5 22:40编辑过]
