ZEROCATH

身无长物江湖远,胸有沟壑天地宽

0%

数据结构——栈的应用之迷宫求解

问题描述

求从迷宫的入口到出口的所有路径。采用穷举法,从入口出发,顺着一方向前进,若能走通则继续向前,否则返回上一位置,向其他方向探索,直到探索到所有可能的通路。

算法描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
设当前位置的初值为入口位置;

do{

若当前位置可通,

则{

将当前位置压至栈顶; // 纳入路径

如果当前位置是出口位置,则结束;

否则切换当前位置的东邻方块为新的当前位置;

}

否则,

若栈不为空且栈顶位置尚有其他方向未经探索,

则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻方块;

若栈不为空且栈顶位置的四周均不可通,

则{

删去栈顶位置;

若栈不为空,则重新测试新的栈顶位置,直至找到一个可通的相邻块或者出栈至栈空;

}

}while(栈不为空);

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<stdio.h>
#include<stdlib.h>
#define MAZE_LINE 10
#define MAZE_ROW 10
#define OVERFLOW -1
#define ERROR 0
#define OK 1
//迷宫地图,' '为通路,'1'为出口标记
char maze_map[MAZE_LINE][MAZE_ROW] = {
{'!','!','!','!','!','!','!','!','!','!'},
{'!',' ',' ','#',' ',' ',' ','#',' ','!'},
{'!',' ',' ','#',' ',' ',' ','#',' ','!'},
{'!',' ',' ',' ',' ','#','#',' ',' ','!'},
{'!',' ','#','#','#',' ',' ',' ',' ','!'},
{'!',' ',' ',' ','#',' ',' ',' ',' ','!'},
{'!',' ','#',' ',' ',' ','#',' ',' ','!'},
{'!',' ','#','#','#',' ','#','#',' ','!'},
{'!','#',' ',' ',' ',' ',' ',' ','1','!'},
{'!','!','!','!','!','!','!','!','!','!'}
};
typedef struct SElemType
{
int ord;//通道块在路径上的序号
int x;
int y;//maze_map[x][y],为通道块的坐标
int direction;//从此块走向下一块的方向
SElemType* next;//
}SElemType;//栈的元素类型

SElemType* initial_stack(SElemType* top);//初始化栈
SElemType* insert_top(SElemType* top);//插入栈顶
SElemType* delete_top(SElemType* top);//删除栈顶
void print_maze_map();//打印地图
int go_to_dirc(SElemType* top);//判断方向dirc是否可通,上下左右分别标记为1,2,3,4
int maze_path(SElemType* top);

int main()
{
SElemType* top=NULL;
printf("初始迷宫地图如下:");
putchar('\n');
print_maze_map();
top = initial_stack(top);
int j = maze_path(top);
if (j)
{
printf("走过迷宫如下:");
putchar('\n');
print_maze_map();
}
print_maze_map();
system("pause");
return 0;
}

SElemType* initial_stack(SElemType* top)
{
SElemType* p;
p = (SElemType*)malloc(sizeof(SElemType));
p->ord = 1;
p->x = 1;
p->y = 1;//入口坐标
p->next = NULL;
p->direction = 0;
top = p;
maze_map[p->x][p->y] = '1';
return top;
//return OK;
}
SElemType* insert_top(SElemType* top)
{
SElemType* p = (SElemType*)malloc(sizeof(SElemType));
if (!p)exit(OVERFLOW);
p->direction = 0;
p->ord = top->ord + 1;
switch (top->direction)
{
case 1:
p->x = top->x - 1; p->y = top->y; break;//新的位块坐标
case 2:
p->x = top->x + 1; p->y = top->y; break;
case 3:
p->x = top->x; p->y = top->y - 1; break;
case 4:
p->x = top->x; p->y = top->y + 1; break;
}
p->next = top;//插入栈顶
top = p;//重置top
if(maze_map[top->x][top->y]!='1')//当不是出口时
maze_map[top->x][top->y] = '|';//在地图上标记走过的位块
return top;
}
SElemType* delete_top(SElemType* top)
{
if (top->next == NULL) exit(OVERFLOW);
SElemType* p;
p = top;
maze_map[top->x][top->y] = 'i';//标记地图上该位块不可通行
top = top->next;
free(p);
top->direction = 0;//重置上一位块的方向
return top;
}
void print_maze_map()//打印地图
{
for (int i = 0; i < MAZE_LINE; i++)
{
for (int j = 0; j < MAZE_ROW; j++)
printf("%2c", maze_map[i][j]);
printf("\n");
}
}
int go_to_dirc(SElemType* top, int dirc)
{
switch (dirc)
{
case 1://向上
if ((top->x >= 0 && maze_map[(top->x) - 1][(top->y)] == ' ')|| (maze_map[(top->x) - 1][(top->y)] == '1'&&top->y!=1))
return 1;
else
return 0;
case 2://向下
if ((top->x + 1 < MAZE_LINE && maze_map[top->x + 1][top->y] == ' ')|| (maze_map[top->x + 1][top->y] == '1'&&top->y!=1))
return 1;
else
return 0;
case 3://向左
if ((top->y - 1 >= 0 && maze_map[top->x][top->y - 1] == ' ')|| (maze_map[top->x][top->y - 1] == '1'&&top->x!=1))
return 1;
else
return 0;
case 4://向右
if ((top->y + 1 < MAZE_ROW && maze_map[top->x][top->y+1] == ' ')|| (maze_map[top->x][top->y + 1] == '1'&&top->x!=1))
return 1;
else
return 0;
default:
return 0;
}
}
int maze_path(SElemType* top)
{
int i = 0;
do
{
for (int i = 1; i <= 4; i++)
if (go_to_dirc(top, i) == 1)//找到一个可通的方向
{
top->direction = i;//
top = insert_top(top);//将该位块插入栈
if (maze_map[top->x][top->y] == '1')
return OK;
i = 0;//重置i,从i=1开始循环
}
if (top->direction == 0 && top != NULL)//栈非空但四周不可通
top = delete_top(top);

} while (top != NULL);
return ERROR;
}

总结与收获

第一道正儿八经自己写完整的题,看书上的算法感觉良好,动起手来才感受得到并不是这样orz。实际操作的过程中深切体会到了自己C语言基础的薄弱,链表的很多操作都不能很好地实现。一遍摸鱼一边写写了将近一天,希望能自己能学好叭.QwQ