数据结构-迷宫_数据结构 迷宫

数据结构作业：用穷举法求迷宫路径

规定：方向的一致性，按照:东南西北四个方向来选择路径。

算法思想

设当前位置的初值为入口位置

do{

​	若当前位置可通（指的是不是城墙）

​		则将当前位置插入栈顶

​		若当前位置等于出口，则结束

​		否则，当前位置变成原来的当前位置的下一个位置。

​	若当前位置不可通

​		若栈不为空，且栈顶元素由其余的方向没被探索，

​			则设定新的当前位置为沿着顺时针方向寻转找到的栈顶元素的下一个相邻块。

​		若栈不为空，且栈顶元素的四个方向均被探索，

​			则{	 	删除栈顶元素，

​					若栈不为空，重新测试新的栈顶位置。

​						直至找到下一个可通的相邻块（有方向没有被寻找到），或者栈空。

​			}

}
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

代码部分

基本完全按照的是当前的算法思想

//MazePath函数
bool MazePath(PosType start, PosType end) {
	PosType curpos = start;Stack S;SELemType e;
	int curstep = 1;InitStack(S);
	do {
		//当前位置不是墙和已经走过的路径
		if (Pass(curpos)) {
			FootPrint(curpos);e.ord = curstep;
			e.seat = curpos;e.di = 1;
			Push(S, e);
			if (IsEqual(curpos,end)) {
				maze[start.x][start.y] = 7;maze[end.x][end.y] = 8;
				PrintMazePath(S);return true;				
			}
			curpos = NextPos(curpos, 1);curstep++;
		}
		//当前位置是墙或者是已经走过的路径
		else {
			if (S.base != S.top) {
				Pop(S, e);
				while (e.di == 4 && (S.base != S.top)) {
					MarkPrint(e.seat); Pop(S, e);//标记这个路线
				}
				if (e.di < 4) {
					e.di++;Push(S, e);
					curpos = NextPos(e.seat, e.di);
				}
			}
		}
	} while (S.top != S.base);
	return false;
}

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

完全代码

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include "my_print.h"
#define N 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
using namespace std;
int maze[N][N];
//迷宫中的二维坐标
typedef struct {
	int x;
	int y;
} PosType;
//栈元素
typedef struct {
	int ord;
	PosType seat;
	int di;//方向
} SELemType;

//栈
typedef struct {
	SELemType* base;
	SELemType* top;
	int stacksize;
} Stack;
//栈的初始化
bool InitStack(Stack& S) {
	S.base = (SELemType*)malloc(sizeof(SELemType) * STACK_INIT_SIZE);
	if (!S.base) return false;
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return true;
}

//栈的push
bool Push(Stack &s,SELemType e){
	//栈满重新分配空间
	if (s.top - s.base >= s.stacksize) {
		s.base = (SELemType*)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SELemType));
		if (!s.base) return false;
		s.top = s.base + s.stacksize;
		s.stacksize += STACKINCREMENT;
	}
	s.top++;
	*s.top = e;
	return true;
}
//栈的pop函数
bool Pop(Stack& s, SELemType& e) {
	//判断栈是否被清空了
	if (s.base == s.top)return false;
	e = *s.top;
	s.top = s.top - 1;
	return true;
}
//输入迷宫
void ScanMaze(int n){
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++)
			scanf_s("%d", &maze[i][j]);
	}
}
//输出迷宫
void PrintMaze(int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)	{
			if (maze[i][j] == 1)
				printf("# ");
            //可以自己更改myPrint，我的这个myPrint只是为了有颜色的变化。
			else if (maze[i][j] == 0)myPrint("· ", DEFAULT," ");
			else if (maze[i][j] == -1) printf("$ ");
			else if (maze[i][j] == 2) /*printf("→ "); */myPrint("→ ", RED, " ");
			else if (maze[i][j] == 3) /*printf("↓ ");*/ myPrint("↓ ", BLUE, " ");
			else if (maze[i][j] == 4) /*printf("← ");*/ myPrint("← ", GREEN, " ");
			else if (maze[i][j] == 5) myPrint("↑ ", DEFAULT,"");
			else if (maze[i][j] == 7) myPrint("S ", DEFAULT, "");
			else if (maze[i][j] == 8) myPrint("E ", DEFAULT, "");
		}
		printf("\n");
	}
}
bool Pass(PosType pos) {
	//为0的时候可以通过，其余的情况下不可以通过
	int curstep = 1;
	if (maze[pos.x][pos.y] == 0) {
		return true;
	}
	return false;
}
void FootPrint(PosType e) {
	maze[e.x][e.y] = 2;
}
void MarkPrint(PosType e) {
	maze[e.x][e.y] = -1;
}
bool IsEqual(PosType a, PosType b) {
	if (a.x == b.x && b.y == a.y)return true;
	else return false;
}
PosType NextPos(PosType e, int i) {
	PosType a;
	a.x = 0;
	a.y = 0;
	switch (i)
	{
	case 1:
		a.x = e.x;
		a.y = e.y+1;
		break;
	case 2:
		a.x = e.x+1;
		a.y = e.y;
		break;
	case 3:
		a.x = e.x;
		a.y = e.y-1;
		break;
	case 4:
		a.x = e.x-1;
		a.y = e.y;
		break;
	default:
		break;
	}
	return a;
}
void PrintMazePath(Stack S1) {
	SELemType e;
	Pop(S1, e);
	while (S1.base != S1.top-1) {
		Pop(S1, e);
		switch (e.di)
		{
		case 1:maze[e.seat.x][e.seat.y] = 2; break;
		case 2:maze[e.seat.x][e.seat.y] = 3; break;
		case 3:maze[e.seat.x][e.seat.y] = 4; break;
		case 4:maze[e.seat.x][e.seat.y] = 5; break;
		default:
			break;
		}
	}
}
bool MazePath(PosType start, PosType end) {
	PosType curpos = start;Stack S;SELemType e;
	int curstep = 1;InitStack(S);
	do {
		//当前位置不是墙和已经走过的路径
		if (Pass(curpos)) {
			FootPrint(curpos);e.ord = curstep;
			e.seat = curpos;e.di = 1;
			Push(S, e);
			if (IsEqual(curpos,end)) {
				maze[start.x][start.y] = 7;maze[end.x][end.y] = 8;
				PrintMazePath(S);return true;				
			}
			curpos = NextPos(curpos, 1);curstep++;
		}
		//当前位置是墙或者是已经走过的路径
		else {
			if (S.base != S.top) {
				Pop(S, e);
				while (e.di == 4 && (S.base != S.top)) {
					MarkPrint(e.seat); Pop(S, e);//标记这个路线
				}
				if (e.di < 4) {
					e.di++;Push(S, e);
					curpos = NextPos(e.seat, e.di);
				}
			}
		}
	} while (S.top != S.base);
	return false;
}

int main() {
	int n;
	printf("请输入迷宫的阶数\n");
	scanf_s("%d", &n);
	ScanMaze(n);
	printf("输入的迷宫为\n");
	PrintMaze(n);
	PosType S ,E;
	printf("请输入迷宫的起点\n");
	scanf_s("%d,%d", &S.x, &S.y);
	printf("请输入迷宫的终点\n");
	scanf_s("%d,%d", &E.x, &E.y);
	if (MazePath(S, E)) {
		printf("结果为\n");
		PrintMaze(n);
	}	
}
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

迷宫数据

1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 1 1
1 0 0 0 1 0 0 0 1 1
1 0 1 0 0 0 1 0 0 1
1 1 1 1 1 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 
1
2
3
4
5
6
7
8
9
10

结果