关于迷宫求解问题（八个方向）
数据结构课程线性结构的一个作业叫作迷宫求解问题，是对于DFS和BFS的考察与应用，
之前在网上找，C语言的都只有四个方向，而这道题要求八个方向，难度更大一些，
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。把代码放在这（比较粗糙），方便自己以后复习。
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 }
这应该不算一篇正式的文章，等寒假再认真写写。
更多精彩
