迷宫问题求解（1） 简单迷宫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Stack.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdlib.h>
#include"Maze.h"
#define MAX 100
typedef struct Position
DataType;
typedef struct Stack
{
int top;
DataType stack[MAX];
}Stack;
void StackInit(Stack* s);
void StackPush(Stack* s, DataType data);
void StackPop(Stack* s);
DataType GetStackTop(Stack*s);
int GetStackSize(Stack*s);
int StackEmpty(Stack *s);

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
#pragma once
//Maze.h
#include <stdio.h>
#include <string.h>
#include <assert.h>
#define ROW 6 
#define COL 6
typedef struct Maze
{
int _map[ROW][COL];
}Maze;
typedef struct Position
{
int _x;
int _y;
}Position;
// 初始化迷宫 
void InitMaze(Maze* m, int map[ROW][COL]);
// 打印迷宫 
void PrintMaze(Maze* m);
// 检测是否为有效入口 
int IsValidEnter(Maze* m, Position enter);
// pos 必须在地图中 pos位置如果是1 
int IsPass(Maze* m, Position pos);
// 检测是否在出口的位置 
int IsExit(Position pos, Position enter);
// 走迷宫 
void PassMaze(Maze* m, Position enter);

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
//Stack.c
#include"Stack.h"
void StackInit(Stack* s)
{
s->top = 0;
}
void StackPush(Stack* s, DataType data)
{
if (s->top == MAX)
{
printf("栈已满！无法入栈元素n");
return;
}
(s->top)++;
s->stack[s->top] = data;
}
void StackPop(Stack *s)
{
if (s->top == 0)
{
printf("栈为空，无法出栈元素n");
return;
}
(s->top)--;
}
DataType GetStackTop (Stack*s)
{
if (s->top == 0)
{
printf("栈为空，无法获取栈顶n");
}
return s->stack[s->top];
}
int GetStackSize(Stack*s)
{
return s->top;
}
int StackEmpty(Stack *s)
{
if (s->top == 0)
{
return 1;
}
else
{
return 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
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
//Maze.c
#include"Maze.h"
#include"Stack.h"
void InitMaze(Maze * m, int map[ROW][COL])
{
int i = 0;
int j = 0;
assert(m);
for (i = 0; i < ROW; i++)
{
for (j = 0; j < COL; j++)
{
m->_map[i][j] = map[i][j];
}
}
}
void PrintMaze(Maze* m)
{
assert(m);
int i = 0;
int j = 0;
for (i = 0; i < ROW; i++)
{
for (j = 0; j < COL; j++)
{
printf(" %d ", m->_map[i][j]);
}
printf("n");
}
}
int IsValidEnter(Maze* m, Position enter)
{
assert(m);
if (enter._x == ROW - 1 || enter._x == 0 || enter._y == COL - 1 || enter._y == 0)
{
return 1;
}
else
return 0;
}
// pos 必须在地图中 pos位置如果是1 
int IsPass(Maze* m, Position pos)
{
assert(m);
if (pos._x >= ROW || pos._x < 0 || pos._y >= COL || pos._y >= COL)
{
return 0;
}
else if (m->_map[pos._x][pos._y] != 1)
{
return 0;
}
else
return 1;
}
// 检测是否在出口的位置 
int IsExit(Position pos, Position enter)
{
if ((pos._x == ROW - 1 || pos._x == 0 || pos._y == COL - 1 || pos._y == 0) && ((pos._x != enter._x) || (pos._y) != enter._y))
{
return 1;
}
return 0;
}
void PassMaze(Maze* m, Position enter)
{
Stack s;
Position cur, next;
if (!IsValidEnter(m, enter))
{
printf("没有入口！n");
return;
}
StackInit(&s);
StackPush(&s, enter);
while (!StackEmpty(&s))
{
cur = GetStackTop(&s);
if (IsExit(cur, enter))
{
return;
}
m->_map[cur._x][cur._y] = 2;
next = cur;
next._x = next._x - 1;
if (IsPass(m, next))
{
StackPush(&s, next);
continue;
}
next._y = next._y - 1;
if (IsPass(m, next))
{
StackPush(&s, next);
continue;
}
next._y = next._y + 1;
if (IsPass(m, next))
{
StackPush(&s, next);
continue;
}
next._x = next._x + 1;
if (IsPass(m, next))
{
StackPush(&s, next);
continue;
}
//cur 四个方向都走不通；
m->_map[cur._x][cur._y] = 3;
StackPop(&s);
}
}

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
//test.c
#include "Maze.h"
#include "Stack.h"
int main()
{
int map[ROW][COL] ={
{ 0,0,0,0,0,0 },
{ 0,0,1,0,0,0 },
{ 0,0,1,0,0,0 },
{ 0,0,1,1,1,0 },
{ 0,0,1,0,1,1 },
{ 0,0,1,0,0,0 }
};
Maze m;
InitMaze(&m, map);
Position enter;
enter._x = 5;
enter._y = 2;
PrintMaze(&m);
PassMaze(&m, enter);
printf("n");
PrintMaze(&m);
system("pause");
return 0;
}