資料結構課程線性結構的一個作業叫作迷宮求解問題，是對于DFS和BFS的考察與應用，
之前在網上找，C語言的都只有四個方向，而這道題要求八個方向，難度更大一些，
把代碼放在這（比較粗糙），方便自己以后復習，
迷宮求解要求：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 #include <string.h> 5 #include<malloc.h> 6 #define LEN 200 7 8 int top; 9 int** maze;//maze為迷宮 10 int** mark;//mark記錄該點是否經過，初值為0，每經過一次加1 11 int m, n;//m為迷宮行數，n為迷宮列數 12 int mov[9][3] = { {0,0,0},{0,0,1},{0,1,1},{0,1,0},{0,1,-1},{0,0,-1},{0,-1,-1},{0,-1,0},{0,-1,1} }; 13 typedef struct body 14 { 15 int i; 16 int j; 17 int v; 18 }body; 19 body* s; 20 21 void produce_maze()//生成迷宮并且初始化mark 22 { 23 srand((unsigned)time(NULL)); 24 int i, j, t; 25 int flag = -1; 26 char c; 27 printf("請輸入迷宮的行數和列數："); 28 scanf_s("%d %d", &m, &n); 29 maze = (int**)malloc(sizeof(int*) * (m + 2)); 30 for (i = 0; i < m + 2; i++) 31 { 32 maze[i] = (int*)malloc(sizeof(int) * (n + 2)); 33 } 34 mark = (int**)malloc(sizeof(int*) * (m + 2)); 35 for (i = 0; i < m + 2; i++) 36 { 37 mark[i] = (int*)malloc(sizeof(int) * (n + 2)); 38 } 39 for (i = 0, t = m + 1, j = 0; j < n + 2; j++) 40 { 41 maze[i][j] = 1; 42 maze[t][j] = 1; 43 } 44 for (i = 1, j = 0, t = n + 1; i < m + 1; i++) 45 { 46 maze[i][j] = 1; 47 maze[i][t] = 1; 48 } 49 while ((flag != 1) && (flag != 0)) 50 { 51 printf("隨機生成請按1，手動生成請按0\n"); 52 scanf_s("%d", &flag); 53 } 54 switch (flag) 55 { 56 case 1: 57 58 for (i = 1; i < m + 1; i++) //隨機生成迷宮 59 { 60 for (j = 1; j < n + 1; j++) 61 { 62 maze[i][j] = rand() % 2; 63 mark[i][j] = 0; 64 } 65 } 66 break; 67 case 0: 68 printf("請輸入迷宮（0表示能通過，1表示不能通過）：\n"); 69 for (i = 1; i < m + 1; i++) //手動生成迷宮 70 { 71 for (j = 1; j < n + 1; j++) 72 { 73 scanf_s(" %c", &c); 74 maze[i][j] = c - '0'; 75 mark[i][j] = 0; 76 } 77 } 78 printf("\n"); 79 break; 80 default: 81 ; 82 } 83 printf("已生成!\n"); 84 printf("\n"); 85 } 86 87 //void setmark() 88 //{ 89 // int i, j; 90 // for (i = 1; i < m + 1; i++) 91 // { 92 // for (j = 1; j < n + 1; j++) 93 // { 94 // mark[i][j] = 0; 95 // } 96 // } 97 //} 98 void setstack()//建立一個長為m*n的堆疊 99 { 100 s = (body*)malloc(sizeof(body) * m * n);//0~mn-1 101 memset(s, 0, sizeof(body) * m * n); 102 top = 0; 103 } 104 105 void Push(int a, int b, int c) 106 { 107 top++; 108 s[top].i = a; 109 s[top].j = b; 110 s[top].v = c; 111 } 112 113 body Pop() 114 { 115 return s[top]; 116 } 117 118 void output(body* s) 119 { 120 int i; 121 for (i = 1; i <= top; i++) { 122 printf("i=%d,j=%d,v=%d\n", s[i].i, s[i].j, s[i].v); 123 } 124 } 125 126 int Empty()//top的值等于堆疊內元素的個數 127 { 128 if (top <= 0) 129 return 1; 130 else 131 return 0; 132 } 133 134 void printmaze()//列印迷宮 135 { 136 int i, j; 137 printf("迷宮如下：\n"); 138 for (i = 0; i < m + 2; i++) 139 { 140 for (j = 0; j < n + 2; j++) 141 { 142 printf("%d ", maze[i][j]); 143 } 144 printf("\n"); 145 } 146 printf("\n"); 147 } 148 149 int DG_maze(int a, int b, int c)//迷宮求解的遞回演算法 150 { 151 if ((maze[a][b] == 1) || (mark[a][b] == 1)) 152 { 153 printf("無路徑！\n"); 154 exit(0); 155 } 156 if ((a == m) && (b == n)) 157 { 158 printf("遞回法，路徑如下:\n"); 159 output(s); 160 printf("\n"); 161 return 0; 162 } 163 if ((maze[a][b + 1] == 0) && (mark[a][b + 1] == 0)) 164 { 165 mark[a][b] = 1; 166 c = 1; 167 Push(a, b, c); 168 DG_maze(a, b + 1, c); 169 return 0; 170 } 171 if ((maze[a + 1][b + 1] == 0) && (mark[a + 1][b + 1] == 0)) 172 { 173 mark[a][b] = 1; 174 c = 2; 175 Push(a, b, c); 176 DG_maze(a + 1, b + 1, c); 177 return 0; 178 } 179 if ((maze[a + 1][b] == 0) && (mark[a + 1][b] == 0)) 180 { 181 mark[a][b] = 1; 182 c = 3; 183 Push(a, b, c); 184 DG_maze(a + 1, b, c); 185 return 0; 186 } 187 if ((maze[a + 1][b - 1] == 0) && (mark[a + 1][b - 1] == 0)) 188 { 189 mark[a][b] = 1; 190 c = 4; 191 Push(a, b, c); 192 DG_maze(a + 1, b - 1, c); 193 return 0; 194 } 195 if ((maze[a][b - 1] == 0) && (mark[a][b - 1] == 0)) 196 { 197 mark[a][b] = 1; 198 c = 5; 199 Push(a, b, c); 200 DG_maze(a, b - 1, c); 201 return 0; 202 } 203 if ((maze[a - 1][b - 1] == 0) && (mark[a - 1][b - 1] == 0)) 204 { 205 mark[a][b] = 1; 206 c = 6; 207 Push(a, b, c); 208 DG_maze(a, b + 1, c); 209 } 210 if ((maze[a - 1][b] == 0) && (mark[a - 1][b] == 0)) 211 { 212 mark[a][b] = 1; 213 c = 7; 214 Push(a, b, c); 215 DG_maze(a - 1, b, c); 216 return 0; 217 } 218 if ((maze[a - 1][b + 1] == 0) && (mark[a - 1][b + 1] == 0)) 219 { 220 mark[a][b] = 1; 221 c = 8; 222 Push(a, b, c); 223 DG_maze(a - 1, b + 1, c); 224 return 0; 225 } 226 else 227 { 228 a = Pop().i; 229 b = Pop().j; 230 c = Pop().v; 231 top--; 232 DG_maze(a, b, c); 233 return 0; 234 } 235 } 236 237 int UDG_maze()//非遞回演算法 238 { 239 int minlength = LEN; 240 int a; 241 int b; 242 int x = 1; 243 int y = 1;//xy表橫縱坐標 244 int z = 1;//表方向 245 int flag = 0;//表有幾條通路 246 mark[1][1] = 1; 247 printf("分析結果如下：\n"); 248 if (maze[x][y] == 1) 249 { 250 printf("迷宮無入口到出口的路經\n"); 251 return 0; 252 } 253 do 254 { 255 a = x + mov[z][1]; 256 b = y + mov[z][2]; 257 if ((maze[a][b] == 0) && (mark[a][b] == 0)) 258 { 259 Push(x, y, z); 260 mark[a][b] = 1; 261 if ((a == m) && (b == n)) 262 { 263 output(s); 264 minlength = (minlength > top ? top : minlength); 265 printf("\n"); 266 printf("***************************\n"); 267 flag++; 268 mark[a][b] = 0; 269 top--; 270 z++; 271 } 272 else 273 { 274 x = a; 275 y = b; 276 z = 1; 277 } 278 } 279 else 280 { 281 if (z < 8) 282 z++; 283 else 284 { 285 if (top > 0) 286 { 287 do { 288 mark[x][y] = 0; 289 x = Pop().i; 290 y = Pop().j; 291 z = Pop().v; 292 z++; 293 top--; 294 } while (z > 8);//連續退堆疊時要注意每一次都要將該點的mark清零！（頭禿啊~~qwq） 295 } 296 else 297 { 298 mark[x][y] = 0; 299 continue; 300 } 301 } 302 } 303 } while (mark[1][1]); 304 if (!flag) 305 { 306 307 printf("迷宮無入口到出口的路經\n"); 308 } 309 else 310 { 311 printf("共%d條通路\n", flag); 312 printf("其中最短路徑長為%d\n", minlength); 313 } 314 } 315 316 int main() 317 { 318 int menu; 319 int status; 320 produce_maze(); 321 printmaze(); 322 setstack(); 323 printf("請選擇遞回演算法or非遞回演算法：（遞回演算法按1，非遞回演算法按0）\n"); 324 scanf_s("%d", &menu); 325 if (menu == 1) 326 { 327 status = DG_maze(1, 1, 0); 328 } 329 else if (menu == 0) 330 { 331 status = UDG_maze(); 332 } 333 else printf("輸入錯誤~親，重來一次吧~"); 334 free(maze); 335 free(mark); 336 return 0; 337 }
這應該不算一篇正式的文章，等寒假再認真寫寫，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102316.html
標籤：其他
上一篇：更改默認路徑安裝，迷茫了
下一篇：PAT乙級1020