스택을 이용한 미로찾기
스택을 이용한 미로찾기입니다.
원리는 매우 간단합니다.
일단 가본 길을 전부 스택에 쌓고 갈수 있는 공간이 없으면
스택의 데이터를 POP하고 위에 작업을 계속 진행합니다.
길이냐 벽이냐는 원핫코딩으로 코딩하였습니다.
|
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
|
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define WIDTH 10
#define HIGH 10
char map[HIGH][WIDTH] = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ –1, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 0, 0, 0, 1 },
{ 1, 1, 2, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
void display(){
int i, j;
for (i = 0; i < HIGH; ++i){
for (j = 0; j < WIDTH; ++j){
switch (map[i][j]){
case –1:
printf(“◇”);
break;
case 1:
printf(“■”);
break;
case 2:
printf(“★”);
break;
case 0:
printf(“□”);
}
}
printf(“\n”);
}
}
typedef struct __POINT
{
int y;
int x;
}point;
typedef struct __STACK
{
struct __STACK * link;
point point;
}stack;
void init(stack ** p_head){
*p_head = NULL;
}
void push(stack **p_head, point point){
stack * temp = (stack*)malloc(sizeof(stack));
if (!temp)
exit(1);
if (*p_head != NULL){
temp–>point = point;
temp–>link = *p_head;
}
else{
temp–>point = point;
temp–>link = NULL;
}
*p_head = temp;
}
point pop(stack **p_head){
if (!p_head)
exit(1);
point point_temp = (*p_head)–>point;
stack * stack_temp = *p_head;
*p_head = (*p_head)–>link;
free(stack_temp);
return point_temp;
}
void show(stack* head){
for (; head; head = head–>link)
printf(“(%d %d)\n”, head–>point.x, head–>point.y);
}
bool stackfree(stack ** p_head){
stack * q = *p_head;
stack * p = NULL;
if (!p_head)
return false;
for (; q; p = q, q = q–>link){
free(p);
}
*p_head = NULL;
}
int main(){
point Location={ 1,0 };
stack *head;
init(&head);
push(&head,Location);
while (map[Location.y + 1][Location.x]!=2){
map[Location.y][Location.x] = –1;
display();
show(head);
//UP
if (map[Location.y + 1][Location.x] != 1 && map[Location.y+1 ][Location.x] !=–1 ){
Location.y++;
push(&head, Location);
}
//DOWN
else if (map[Location.y – 1][Location.x] != 1 && map[Location.y–1][Location.x] != –1){
Location.y––;
push(&head, Location);
}
//LEFT
else if (map[Location.y][Location.x – 1] != 1 && map[Location.y][Location.x–1] != –1){
Location.x––;
push(&head, Location);
}
//RIGHT
else if (map[Location.y][Location.x + 1] != 1 && map[Location.y][Location.x+1] != –1){
Location.x++;
push(&head, Location);
}
//실패시
else{
Location = pop(&head);
}
system(“pause”);
system(“cls”);
}
printf(“목적지 도착”);
display();
stackfree(&head);
}
|
cs |