迷宫问题的解决方法

 1 #include<stdio.h>
 2 #include <stdlib.h> 
 3 int visit(int, int);
 4 int maze[11][10] =
 5 {
 6     {1, 1, 1, 1, 1, 1, 1, 1, 1 ,1},
 7     {1, 0, 0, 1, 0, 0, 0, 1, 0 ,1},
 8     {1, 0, 0, 1, 0, 0, 0, 1, 0 ,1},
 9     {1, 0, 0, 0, 0, 1, 1, 0, 1 ,1},
10     {1, 0, 1, 1, 1, 0, 0, 1, 0 ,1},
11     {1, 0, 0, 0, 1, 0, 0, 0, 0 ,1},
12     {1, 0, 1, 0, 0, 0, 1, 0, 1 ,1},
13     {1, 0, 1, 1, 1, 1, 0, 0, 1 ,1},
14     {1, 1, 1, 0, 0, 0, 1, 0, 1 ,1},
15     {1, 1, 1, 0, 0, 0, 0, 0, 0, 1},
16     {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
17 };
18 int startI = 1, startJ = 1; // 入口
19 int endI = 9, endJ = 8; // 出口
20 int success = 0;
21 
22 int main(void) {
23     int i, j;
24 
25     printf("显示迷宫：
");
26     for (i = 0; i < 9; i++) {
27         for (j = 0; j < 8; j++)
28             if (maze[i][j] == 1)
29                 printf("■");
30             else
31                 printf("  ");
32         printf("
");
33     }
34 
35     if (visit(startI, startJ) == 0)
36         printf("
沒有找到出口！
");
37     else {
38         printf("
显示路径：
");
39         for (i = 0; i < 9; i++) {
40             for (j = 0; j < 8; j++) {
41                 if (maze[i][j] == 1)
42                     printf("■");
43                 else if (maze[i][j] == 2)
44                     printf("▲");
45                 else
46                     printf("  ");
47             }
48             printf("
");
49         }
50     }
51 
52     return 0;
53 }
54 
55 int visit(int i, int j) {
56     maze[i][j] = 2;
57 
58     if (i == endI && j == endJ)
59         success = 2;
60 
61     if (success != 2 && maze[i][j + 1] == 0) visit(i, j + 1);
62     if (success != 2 && maze[i + 1][j] == 0) visit(i + 1, j);
63     if (success != 2 && maze[i][j - 1] == 0) visit(i, j - 1);
64     if (success != 2 && maze[i - 1][j] == 0) visit(i - 1, j);
65 
66     if (success != 2)
67         maze[i][j] = 0;
68 
69     return success;
70 }

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef enum { ERROR, OK } Status;
  4 typedef struct
  5 {
  6     int row, line;
  7 }PosType;
  8 
  9 typedef struct
 10 {
 11     int  di, ord;
 12     PosType seat;
 13 }SElemType;
 14 
 15 typedef struct
 16 {
 17     SElemType * base;
 18     SElemType * top;
 19     int        stacksize;
 20 }SqStack;
 21 
 22 Status InitStack(SqStack &S);
 23 Status Push(SqStack &S, SElemType &a);
 24 Status Pop(SqStack &S, SElemType &a);
 25 Status StackEmpty(SqStack S);
 26 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end);
 27 void Initmaze(int maze[12][12], int size);
 28 void printmaze(int maze[12][12], int size);
 29 Status Pass(int maze[12][12], PosType CurPos);
 30 void Markfoot(int maze[12][12], PosType CurPos);
 31 PosType NextPos(PosType CurPos, int Dir);
 32 void printpath(int maze[12][12], SqStack S, int size);
 33 void main(void)
 34 {
 35     SqStack S;
 36     int size, maze[12][12];
 37     for (int n = 0; n < 10; n++)
 38     {
 39         printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):
");
 40         scanf("%d", &size);
 41         if (size < 1 || size>10)
 42         { 
 43             printf("输入错误!");
 44             return;
 45         }
 46         Initmaze(maze, size);
 47         printmaze(maze, size);
 48         PosType start, end;
 49         printf("输入入口行坐标和列坐标:");
 50         scanf("%d", &start.row); 
 51         scanf("%d", &start.line);
 52         printf("输入出口行坐标和列坐标:");
 53         scanf("%d", &end.row);
 54         scanf("%d", &end.line);
 55         if (MazePath(maze, S, start, end))
 56             printpath(maze, S, size);
 57         else
 58             printf("找不到通路!

");
 59     }
 60 }
 61 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end)
 62 {
 63     PosType curpos;
 64     int curstep;
 65     SElemType e;
 66     InitStack(S);
 67     curpos = start;
 68     curstep = 1;
 69     do {
 70         if (Pass(maze, curpos))
 71         {
 72             Markfoot(maze, curpos);
 73             e.di = 1;
 74             e.ord = curstep;
 75             e.seat = curpos;
 76             Push(S, e);
 77             if (curpos.row == end.row && curpos.line == end.line)
 78                 return OK;
 79             curpos = NextPos(curpos, 1);
 80             curstep++;
 81         }
 82         else
 83         {
 84             if (!StackEmpty(S))
 85             {
 86                 Pop(S, e);
 87                 while (e.di == 4 && !StackEmpty(S))
 88                 {
 89                     Markfoot(maze, e.seat);
 90                     Pop(S, e);
 91                 }
 92                 if (e.di < 4)
 93                 {
 94                     e.di++;
 95                     Push(S, e);
 96                     curpos = NextPos(e.seat, e.di);
 97                 }
 98             }
 99         }
100     } while (!StackEmpty(S));
101     return ERROR;
102 }
103 void Initmaze(int maze[12][12], int size)
104 {
105     char select;
106     printf("选择创建方式 A:自动生成 B:手动创建
");
107 label:scanf("%c", &select);
108     if (select == 'a' || select == 'A')
109     {
110         for (int i = 0; i < size + 2; i++)maze[0][i] = 1;
111         for (int i = 1; i < size + 1; i++)
112         {
113             maze[i][0] = 1;
114             for (int j = 1; j < size + 1; j++)
115                 maze[i][j] = rand() % 2;
116             maze[i][size + 1] = 1;
117         }
118         for (int i = 0; i < size + 2; i++)maze[size + 1][i] = 1;
119     }
120     else if (select == 'b' || select == 'B')
121     {
122         printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):
", size, size);
123         for (int i = 0; i < size + 2; i++)maze[0][i] = 1;
124         for (int i = 1; i < size + 1; i++)
125         {
126             maze[i][0] = 1;
127             for (int j = 1; j < size + 1; j++)
128                 scanf("%d", &maze[i][j]);
129             maze[i][size + 1] = 1;
130         }
131         for (int i = 0; i < size + 2; i++)maze[size + 1][i] = 1;
132     }
133     else if (select == '
')goto label;
134     else printf("输入错误!");
135 }
136 void printmaze(int maze[12][12], int size)
137 {
138     printf("

");
139     printf("显示所建的迷宫(#表示外面的墙):
");
140     for (int i = 0; i < size + 2; i++)
141         printf("%c ", '#');
142     printf("
");
143     for (int i = 1; i < size + 1; i++)
144     {
145         printf("%c ", '#');
146         for (int j = 1; j < size + 1; j++)
147         {
148             printf("%d ", maze[i][j]);
149         }
150         printf("%c", '#');
151         printf("
");
152     }
153     for (int i = 0; i < size + 2; i++)printf("%c ", '#'); printf("
");
154 
155 }
156 
157 void printpath(int maze[12][12], SqStack S, int size)
158 {
159     printf("

通路路径为:
");
160     SElemType * p = S.base;
161     while (p != S.top)
162     {
163         maze[p->seat.row][p->seat.line] = 2;
164         p++;
165     }
166     for (int i = 0; i < size + 2; i++)
167         printf("%c ", '#'); printf("
");
168     for (int i = 1; i < size + 1; i++)
169     {
170         printf("%c ", '#');
171         for (int j = 1; j < size + 1; j++)
172         {
173             if (maze[i][j] == 2) 
174                 printf("%c ", '0');
175             else              
176                 printf(" ");
177         }
178         printf("%c", '#');
179         printf("
");
180     }
181     for (int i = 0; i < size + 2; i++)
182         printf("%c ", '#'); 
183     printf("

");
184 
185 }
186 
187 Status Pass(int maze[12][12], PosType CurPos)
188 {
189     if (maze[CurPos.row][CurPos.line] == 0)
190         return OK;
191     else 
192         return ERROR;
193 }
194 void Markfoot(int maze[12][12], PosType CurPos)
195 {
196     maze[CurPos.row][CurPos.line] = 1;
197 }
198 PosType NextPos(PosType CurPos, int Dir)
199 {
200     PosType ReturnPos;
201     switch (Dir)
202     {
203     case 1:
204         ReturnPos.row = CurPos.row;
205         ReturnPos.line = CurPos.line + 1;
206         break;
207     case 2:
208         ReturnPos.row = CurPos.row + 1;
209         ReturnPos.line = CurPos.line;
210         break;
211     case 3:
212         ReturnPos.row = CurPos.row;
213         ReturnPos.line = CurPos.line - 1;
214         break;
215     case 4:
216         ReturnPos.row = CurPos.row - 1;
217         ReturnPos.line = CurPos.line;
218         break;
219     }
220     return ReturnPos;
221 }
222 Status InitStack(SqStack &S)
223 {
224     S.base = (SElemType *) malloc(100 * sizeof(SElemType));
225     if (!S.base)return ERROR;
226     S.top = S.base;
227     S.stacksize = 100;
228     return OK;
229 }
230 Status Push(SqStack &S, SElemType &a)
231 {
232     *S.top++ = a;
233     return OK;
234 }
235 Status Pop(SqStack &S, SElemType &a)
236 {
237     if (S.top == S.base)
238         return ERROR;
239     a = *--S.top;
240     return OK;
241 }
242 
243 Status StackEmpty(SqStack S)
244 {
245     if (S.top == S.base)
246         return OK;
247     return ERROR;
248 }