1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "sqstack.h" //引入顺序栈储存结构及其基本操作
4 #define MAXLENGTH 25 //设迷宫最大行列为25
5 #define ERROR 0
6 #define OK 1
7 #define TRUE 1
8 #define FALSE 0
9 typedef int Status;
10 typedef int MazeType[MAXLENGTH][MAXLENGTH]; //迷宫数组[行][列]
11 PosType begin, end; //迷宫入口坐标，出口坐标
12 PosType direc[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}，移动方向依次为东南西北
13 MazeType maze; //迷宫数组
14 int x, y;//迷宫的行，列
15 int curstep = 1; //当前足迹，初值在入口处为1
16 struct SElemType
17 {
18 int ord; //通道块在路径上的“序号”
19 PosType seat; //通道块在迷宫中的“坐标位置”
20 int di; //从此通道块走向下一通道块的“方向”(0-3表示东-北)
21 };
22 void Print() {
23 //输出迷宫结构
24 int i, j;
25 for (i = 0; i < x; i++)
26 {
27 for (j = 0; j < y; j++)
28 printf("%3d", maze[i][j]);
29 printf("\n");
30 }
31 }
32 void Init()
33 {
34 //设定迷宫布局(墙值为0，通道值为1)
35 //全局变量maze 未初始化 所以均为值均为0
36 int i, j, x1, y1;
37 printf("请输入迷宫的行数，列数(包括外墙):");
38 scanf("%d%d", &x, &y);
39 for (i = 1; i < x - 1; i++)
40 for (j = 1; j < y - 1; j++)
41 maze[i][j] = 1; //定义通道初值为1
42 printf("请输入迷宫内墙单元数:");
43 scanf("%d", &j);
44 printf("请依次输入迷宫内墙每个单元的行数，列数:\n");
45 //FILE *fp; 注释掉的这五行之前是方便我调试的
46 //fp = fopen("maze.txt", "r");
47 //int *px1 = &x1, *py1 = &y1;
48 for(i=1;i<=j;i++)
49 {
50 //fscanf(fp, "%d%d", px1, py1);
51 //maze[x1][y1] = 0;
52 scanf("%d%d", &x1, &y1);
53 maze[x1][y1] = 0; //定义墙值为0
54 }
55 printf("迷宫结构如下:\n");
56 Print();
57 printf("请输入入口的行数，列数:");
58 scanf("%d%d", &begin.x, &begin.y);
59 printf("请输入出口的行数，列数:");
60 scanf("%d%d", &end.x, &end.y);
61 }
62 void MarkPrint(PosType seat)
63 {//标记迷宫块不可通过
64 maze[seat.x][seat.y] = -1;
65
66
67 }
68 Status Pass(PosType b)
69 {
70 //当迷宫m的b点的值为1，return OK;
71 //否则return ERROR;
72 if (maze[b.x][b.y] == 1)
73 return OK;
74 else
75 return ERROR;
76 }
77 void FootPrint(PosType b)
78 {
79 //使迷宫m的b点的值变为足迹(curstep),表示经过
80 maze[b.x][b.y] = curstep;
81
82 }
83 PosType NextPos(PosType b,int di)
84 {
85 //根据当前位置b及其移动方向di，修改b为下一位置
86 b.x += direc[di].x;
87 b.y += direc[di].y;
88 return b;
89 }
90 Status MazePath(PosType start, PosType end)
91 {
92 //若迷宫m中存在从入口start到出口end的通道
93 //则求得一条存放在栈中，并返回TRUE；否则返回FAlSE
94 SqStack s,*S; //顺序栈
95 S = &s;
96 PosType curpos;
97 StackType e,*pe;
98 pe = &e;
99 InitStack(S);
100 curpos = start;
101 do
102 {
103 if (Pass(curpos)) //当前可以通过，则是未曾走到的通道块
104 {
105 FootPrint(curpos); //留下足迹
106 e.ord = curstep; //栈元素序号为当前序号
107 e.seat = curpos; //栈元素位置为当前位置
108 e.di = 0; //从当前位置出发，下一位置为东
109 Push(S, e); //入栈当前位置及其状态
110 curstep++; //足迹加1
111 if (curpos.x == end.x&&curpos.y == end.y) //到达出口
112 return TRUE;
113 curpos = NextPos(curpos, e.di); //由当前位置及移动方向确定下一个当前位置
114 }
115 else //当前位置不能通过
116 if (!EmptyStack(S)) //栈不为空
117 {
118 Pop(S, pe); // 退栈到前一位置
119 curstep--; //足迹减1
120 while (e.di == 3 && !EmptyStack(S)) //前一位置处于最后一个方向(北)
121 {
122 MarkPrint(e.seat); //留下不能通过的标记(-1)
123 Pop(S, pe); //退一步
124 curstep--; //足迹再减1
125
126 }
127 if (e.di < 3) //没有到最后一个方向(北)
128 {
129 e.di++; //换下一个方向探索
130 Pu