相关背景
去年 C 程序设计专题的第一个 Project （模块化程序设计与递归函数专题），当时出于一种拿高分+逼格的目的，写了两个版本—— Console 版和 GUI 版。
Project 的要求就是用递归求解平面迷宫问题（或者用递归求解 N 皇后问题），然后再无其他限制。
当时在老师提及八皇后问题后，已经尝试写过若干个版本的 N 皇后了，所以 Project 就选择了迷宫问题。
效果图
Console 版
GUI 版（EGE实现）
感想
怎么说呢，在当时，对我而言，这也算是有一定的难度的。当时最为繁琐的就是图形库的选择与图形化的实现，尤其是图形库的选择过程。当时尝试了GTK+, SDL, easyX, EGE，最后只有 easyX 和 EGE 能在我的电脑上正常的使用。然后又听说 EGE 的效率比 easyX 高，于是便选择了 EGE ，看了大约两个小时文档（然后发现几乎都没用到），最后写出了 GUI 版的 Project。
然后为了演示的效果，又用深度优先搜索实现了迷宫的自动生成。最终与基于递归实现的迷宫寻径整合到一起，实现了这个 Project。
具体实现及思路
采用一个全局的动态二维数组用于储存迷宫信息（如下表所示），同时记录墙体与空间位置。然后用若干个结构体记录坐标。
| 墙 | 起 | 墙 | 墙 | 墙 |
| 墙 | 空 | 墙 | 空 | 终 |
| 墙 | 空 | 墙 | 空 | 墙 |
| 墙 | 空 | 空 | 空 | 墙 |
| 墙 | 墙 | 墙 | 墙 | 墙 |
迷宫生成的方式，则是参考了 Wikipedia 的描述，首先将原始迷宫初始化为一张完全方格图，然后设定起点和终点，从起点开始进行深度优先搜索，每次遍历的方向与步数都随机取值，途中遇能拆的墙（墙对面有未遍历过的空间）则“拆墙”（将该位置改为空余的空间），直至遍历全图。
至于路经的寻找则是用相对简单的递归实现的（实际也是一个深度优先搜索，其实用广度优先搜索效率会高一些？，但是题目要求使用递归实现），一个简简单单的回溯过程。将终点位置作为递归出口，递推关系为相邻两空余点间的水平或垂直移动——若可以从当前坐标移动到某一相邻坐标（墙壁或路径点或标记不可通点为无法移动到的点），则将该点标记为路径点，从可移动位置进行下一轮的移动；若从当前点无法移动到其所有相邻的坐标，则将改点标记为不可通点，从当前函数返回，继续进行上一路径点所对应的移动过程。以此类推，在迷宫可通、迷宫大小合适的情况下，必然可得出至少一个可行解。（这一段是当时在报告上写的，直接了粘贴过来）这种思路很简单，可惜递归的实现一点都不优雅，当问题规模增大时，必然会堆栈溢出。尽管当时我的能力足以实现一个模拟堆栈的版本，但精力有限（总不能将时间都耗在这门课上），未去实现。
（差不多都忘了……早知当时就该顺手更新上来的）
源码
有点惨不忍睹……算是自己的黑历史吧。。。
当时交的版本随机遍历以生成迷宫，未采用 DFS
（当时写的修改版中函数竟然用的是 ‘dps’ 什么鬼(⊙﹏⊙)）
Console 版（上交时的格式）
|
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 |
/* Name: Maze-In-Console * ############################################ * Author: LLonely * ID: xxx（删掉了） * Email: i#llonely.com * Website: llonely.com * -------------------------------------------- * Maze-Core & Maze-Console-Dynamic-Expression & Maze-Random-Generator */ #include<stdio.h> #include<stdlib.h> #include<time.h> #include<windows.h> #define WALL -1 #define START -3 #define END -4 #define NOTWAY -2 #define MX 39 #define MY 149 #define _Y (MY*2+1) #define _X (MX*2+1) #define PERR(bSuccess, api){if(!(bSuccess)) printf("%s:Error %d from %s \ on line %d\n", __FILE__, GetLastError(), api, __LINE__);} // int maze[MY*2+1][MX*2+1],sign=1,_x=0,_y=0; int **maze,sign=1,_x=0,_y=0; unsigned long speed=50; struct position { int x; int y; }direction[]={{1,0},{-1,0},{0,1},{0,-1}},maker,temp,explorer; void gotoxy(int x, int y) { CONSOLE_SCREEN_BUFFER_INFO csbiInfo; HANDLE hConsoleOut; hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE); GetConsoleScreenBufferInfo(hConsoleOut, &csbiInfo); csbiInfo.dwCursorPosition.X = x; csbiInfo.dwCursorPosition.Y = y; SetConsoleCursorPosition(hConsoleOut, csbiInfo.dwCursorPosition); } void cls(HANDLE hConsole) { COORD coordScreen = { 0, 0 }; BOOL bSuccess; DWORD cCharsWritten; CONSOLE_SCREEN_BUFFER_INFO csbi; DWORD dwConSize; bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi ); PERR( bSuccess, "GetConsoleScreenBufferInfo" ); dwConSize = csbi.dwSize.X * csbi.dwSize.Y; bSuccess = FillConsoleOutputCharacter( hConsole, (TCHAR) ' ', dwConSize, coordScreen, &cCharsWritten ); PERR( bSuccess, "FillConsoleOutputCharacter" ); bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi ); PERR( bSuccess, "ConsoleScreenBufferInfo" ); bSuccess = FillConsoleOutputAttribute( hConsole, csbi.wAttributes, dwConSize, coordScreen, &cCharsWritten ); PERR( bSuccess, "FillConsoleOutputAttribute" ); bSuccess = SetConsoleCursorPosition( hConsole, coordScreen ); PERR( bSuccess, "SetConsoleCursorPosition" ); return; } int can_move(int y,int x) { if(y<0||x<0||x>=_x||y>=_y) return 0; else if(maze[y][x]==WALL||maze[y][x]==NOTWAY||maze[y][x]==START||maze[y][x]>0) return 0; else return 1; } void print_solution(void) { int i,j,max=0; HANDLE hConsoleOut; hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE); /* struct step { int y; int x; }steps[_X*_Y+1],end;*/ struct step { int y; int x; }*steps,end; steps=(struct step*)calloc(_y*_x+1,sizeof(struct step)); for(i=0;i<_y;i++) { for(j=0;j<_x;j++) { if(maze[i][j]==WALL) printf("%c",'#'); else if(maze[i][j]>0) { steps[maze[i][j]].y=i; steps[maze[i][j]].x=j; if(maze[i][j]>max) max=maze[i][j]; printf(" "); } else if(maze[i][j]==END) { end.y=i; end.x=j; printf("D"); } else printf(" "); } printf("\n"); } SetConsoleTextAttribute(hConsoleOut, FOREGROUND_RED|FOREGROUND_INTENSITY); if(_x*_y>=2000) speed=25; if(_x*_y>=5000) speed=10; for(i=1;i<=max;i++) { gotoxy(steps[i].x,steps[i].y); printf("*"); Sleep(speed); } gotoxy(end.x,end.y); printf("Y"); SetConsoleTextAttribute(hConsoleOut,FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return ; } int move(int n) { int i,j; if(maze[explorer.y][explorer.x]==END) { print_solution(); gotoxy(_x+1,_y); printf("\nPress Enter to exit."); getchar(); exit(0); } maze[explorer.y][explorer.x]=n; for(i=0;i<4;i++) { if(can_move(explorer.y+direction[i].y,explorer.x+direction[i].x)) { explorer.y+=direction[i].y; explorer.x+=direction[i].x; move(n+1); maze[explorer.y][explorer.x]=NOTWAY; explorer.y-=direction[i].y; explorer.x-=direction[i].x; } } maze[explorer.y][explorer.x]=NOTWAY; } int is_map_created() { int i,j,x,y; x=_x; y=_y; for(i=1;i<y-1;i+=2) for(j=1;j<x-1;j+=2) if(maze[i][j]==0) { temp.y=i; temp.x=j; return 0; } return 1; } int can_go(int x,int y) { if(x<1||y<1||x>=_x||y>=_y) return 0; else if(maze[y][x]>0) return 0; return 1; } int can_set(int x,int y) { if(x<1||y<1||x>=_x||y>=_y) return 0; else if(maze[y][x]<1) return 0; return 1; } void print_maze() { int i,j,x,y; x=_x; y=_y; for(i=0;i<y;i++) { for(j=0;j<x;j++) { if(maze[i][j]==WALL) { printf("#"); } else printf(" "); } printf("\n"); } } int make_map() { int step,i,direction_random,count=0; maze[maker.y][maker.x]=sign; for(i=0;i<4;i++) { if(can_go(maker.x+2*direction[i].x,maker.y+2*direction[i].y)) { count++; } } if(count==0) return 0; step=rand()%3+1; direction_random=rand()%4; for(i=0;i<step;i++) { if(can_go(maker.x+2*direction[direction_random].x,maker.y+2*direction[direction_random].y)) { maze[maker.y+direction[direction_random].y][maker.x+direction[direction_random].x]=sign; maze[maker.y+2*direction[direction_random].y][maker.x+2*direction[direction_random].x]=sign; maker.x+=2*direction[direction_random].x; maker.y+=2*direction[direction_random].y; } else { direction_random=rand()%4; } } return 1; } int complete_map(void) { int i; for(i=0;i<4;i++) { if(can_set(maker.x+2*direction[i].x,maker.y+2*direction[i].y)) { maze[maker.y+direction[i].y][maker.x+direction[i].x]=sign+1; return 1; } } return 0; } int main(int argc,char *argv[]) { int i,j,x,y,s,e,*p_temp; char num[10]; HANDLE hConsoleOut; hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE); if(argc>=3) { _y=2*atoi(argv[2])+1; _x=2*atoi(argv[1])+1; } else if(argc==2) { _y=_x=2*atoi(argv[1])+1; } else { _y=_Y; _x=_X; } if(_y<1||_x<1||_x>79||_y>300) { printf("Error!"); return 1; } maze=(int **)calloc(_y,sizeof(int *)); p_temp=(int *)calloc(_x*_y,sizeof(int)); for(i=0;i<_y;i++) { maze[i]=p_temp+i*_x; } x=_x; y=_y; cls(hConsoleOut); for(i=0;i<y;i++) { for(j=0;j<x;j++) { maze[i][j]=!(j%2)||!(i%2)||i==0||i==y-1?WALL:0; } } maker.y=1; maker.x=1; srand(time(NULL)); while(!is_map_created()) { while(make_map()) ; sign++; maker=temp; if(sign>=3) complete_map(); } maker=temp; if(sign>=3) complete_map(); for(i=0;i<y;i++) for(j=0;j<x;j++) if(maze[i][j]>0) maze[i][j]=0; srand(time(NULL)); s=rand()%(x-2)+1; e=rand()%(x-2)+1; explorer.x=s; explorer.y=0; maze[0][s]=START; maze[y-1][e]=END; move(1); printf("Error!\n"); return 1; } |
GUI 版（还有一个 Res 目录存放了实现动画的图片）
|
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 |
/* Name: Maze-With-Gui * ############################################ * Author: LLonely * ID: Deleted * Email: i#llonely.com * Website: llonely.com * Powered by Ege Gprahics */ #include<stdlib.h> #include<stdio.h> #include<time.h> #include "graphics.h" #define WALL -1 #define START -3 #define END -4 #define NOTWAY -2 #define MX 60 #define MY 60 #define _Y (MY*2+1) #define _X (MX*2+1) // int maze[MY * 2 + 1][MX * 2 + 1], sign = 1, sign_old; int ** maze, sign = 1; int _x, _y, mx, my; struct position { int x; int y; }direction[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, maker, temp, explorer; int can_move(int y, int x) { if (y<0 || x<0 || x >= _x || y >= _x) return 0; else if (maze[y][x] == WALL || maze[y][x] == NOTWAY || maze[y][x] == START || maze[y][x]>0) return 0; else return 1; } int draw_arrow(int x, int y, int r, int direction) { switch (direction) { case 0: line(x - r, y, x + r, y); line(x, y - r, x + r, y); line(x, y + r, x + r, y); break; case 1: line(x - r, y, x + r, y); line(x, y - r, x - r, y); line(x, y + r, x - r, y); break; case 2: line(x, y - r, x, y + r); line(x - r, y, x, y + r); line(x + r, y, x, y + r); break; case 3: line(x, y - r, x, y + r); line(x - r, y, x, y - r); line(x + r, y, x, y - r); break; default: return 0; break; } return 1; } void printf_pad(void) { int i, j; int max = 0; int x, y; char res[20] = "res/res-1.png"; /* struct step { int y; int x; }steps[_x*_x + 1], end;*/ struct step { int y; int x; }*steps, end; steps = (struct step *)malloc((_x*_x + 1)*sizeof(struct step)); x = mx * 2 + 1; y = my * 2 + 1; initgraph(605, 605); setbkcolor(WHITE); setcolor(BLACK); setcaption("Maze"); for (j = 0; j < y; j += 2) for (i = 1; i < x - 1; i += 2) if (maze[j][i] == WALL) line(2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx); for (j = 0; j < x; j += 2) for (i = 1; i < y - 1; i += 2) if (maze[i][j] == WALL) line(2 + (j / 2) * 600.0 / mx, 2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx); for (i = 0; i<_x; i++) { for (j = 0; j<_x; j++) { if (maze[i][j] == WALL) ; else if (maze[i][j]>0) { steps[maze[i][j]].y = i; steps[maze[i][j]].x = j; if (maze[i][j]>max) max = maze[i][j]; } else if (maze[i][j] == END) { end.y = i; end.x = j; steps[max + 1].y = i; steps[max + 1].x = j; } else ; } } setcolor(RED); for (i = 1; i <= max; i++) { if (steps[i].x % 2 && steps[i].y % 2) { for (j = 0; j < 4; j++) { if (steps[i].x + direction[j].x == steps[i + 1].x&&steps[i].y + direction[j].y == steps[i + 1].y) break; } draw_arrow(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1 + (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9, j); //circle(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1+ (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9); Sleep(20); } } PIMAGE image[6], screen; screen = newimage(); getimage(screen, 0, 0, 605, 605); for (i = 0; i < 6; i++) { image[i] = newimage(); getimage(image[i], res, 0, 0); res[8] += 1; } setfont(60, 0, "宋体"); setbkmode(TRANSPARENT); settextjustify(CENTER_TEXT, CENTER_TEXT); for (i = 0; i < 4; i++) { for (j = 0; j < 6; j++) { setfont(60 + ((j == 2 || j == 5) ? 0 : 1) * 10, 0, "宋体"); outtextxy(303, 250, "SUCCESS"); putimage_withalpha(NULL, image[j], 100, 305); //putimage(100, 200, image[j], SRCINVERT); if (j == 2 || j == 5) Sleep(150); Sleep(200); //cleardevice(); putimage(0, 0, screen); } } putimage(0, 0, screen); getch(); closegraph(); return; } int move(int n) { int i; if (maze[explorer.y][explorer.x] == END) { printf_pad(); //getchar(); exit(0); } maze[explorer.y][explorer.x] = n; for (i = 0; i<4; i++) { if (can_move(explorer.y + direction[i].y, explorer.x + direction[i].x)) { explorer.y += direction[i].y; explorer.x += direction[i].x; move(n + 1); maze[explorer.y][explorer.x] = NOTWAY; explorer.y -= direction[i].y; explorer.x -= direction[i].x; } } maze[explorer.y][explorer.x] = NOTWAY; return 0; } int is_map_created() { int i, j, x, y; x = mx * 2 + 1; y = my * 2 + 1; for (i = 1; i<y - 1; i += 2) for (j = 1; j<x - 1; j += 2) if (maze[i][j] == 0) { temp.y = i; temp.x = j; return 0; } return 1; } int can_go(int x, int y) { if (x<1 || y<1 || x >= mx * 2 + 1 || y >= my * 2 + 1) return 0; else if (maze[y][x]>0) return 0; return 1; } int can_set(int x, int y) { if (x<1 || y<1 || x >= mx * 2 || y >= my * 2) return 0; else if (maze[y][x]<1) return 0; return 1; } void print_maze() { int i, j, x, y; x = mx * 2 + 1; y = my * 2 + 1; for (i = 0; i<y; i++) { for (j = 0; j<x; j++) { if (maze[i][j] == WALL) { printf("#"); } else printf(" "); } printf("\n"); } } int make_map() { int step, i, direction_temp, count = 0, d; maze[maker.y][maker.x] = sign; for (i = 0; i<4; i++) { if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y)) { count++; } } if (count == 0) return 0; step = rand() % 3 + 1; direction_temp = rand() % 4; for (i = 0; i<step; i++) { if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y)) { maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign; maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign; maker.x += 2 * direction[direction_temp].x; maker.y += 2 * direction[direction_temp].y; } else { d = rand() % 4; direction_temp = d; } } return 1; } int com_map() { int i; for (i = 0; i<4; i++) { if (can_set(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y)) { maze[maker.y + direction[i].y][maker.x + direction[i].x] = sign + 1; return 1; } } return 0; } int main() { int i, j, x, y, s, e; int *p_temp; char str[10]; setinitmode(NULL); initgraph(400, 300); setcaption("MAZE"); inputbox_getline("请输入迷宫的大小","请输入一个数字，输入完请回车",str,sizeof(str) / sizeof(*str)); mx = my = atoi(str); if (mx<1 || mx>200) { mx = MX; my = MY; _x = _X; _y = _Y; } else { _x = mx * 2 + 1; _y = my * 2 + 1; } x = mx * 2 + 1; y = my * 2 + 1; closegraph(); maze = (int **)calloc(y, sizeof(int *)); p_temp = (int *)calloc(x*y, sizeof(int)); for (i = 0; i<y; i++) { maze[i] = p_temp + x*i; } for (i = 0; i<y; i++) { for (j = 0; j<x; j++) { maze[i][j] = !(j % 2) || !(i % 2) || i == 0 || i == y - 1 ? WALL : 0; } } maker.y = 1; maker.x = 1; srand(time(NULL)); while (!is_map_created()) { while (make_map()) ; sign++; maker = temp; if (sign >= 3) com_map(); } maker = temp; if (sign >= 3) com_map(); //print_maze(); for (i = 0; i<y; i++) for (j = 0; j<x; j++) if (maze[i][j]>0) maze[i][j] = 0; srand(time(NULL)); s = rand() % (mx); e = rand() % (mx); explorer.x = 2 * s + 1; explorer.y = 0; maze[0][2 * s + 1] = START; maze[y - 1][2 * e + 1] = END; move(1); return 0; } |
采用 DFS 的 GUI 版
|
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 |
#include<stdlib.h> #include<stdio.h> #include<time.h> #include "graphics.h" #define WALL -1 #define START -3 #define END -4 #define NOTWAY -2 #define MX 60 #define MY 60 #define _Y (MY*2+1) #define _X (MX*2+1) // int maze[MY * 2 + 1][MX * 2 + 1], sign = 1, sign_old; int ** maze, sign = 1, maker_n = 1, *maker_step, i_maker_step = -1; int _x, _y, mx, my; struct position { int x; int y; }direction[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, maker, temp, explorer; int can_move(int y, int x) { if (y<0 || x<0 || x >= _x || y >= _x) return 0; else if (maze[y][x] == WALL || maze[y][x] == NOTWAY || maze[y][x] == START || maze[y][x]>0) return 0; else return 1; } int draw_arrow(int x, int y, int r, int direction) { switch (direction) { case 0: line(x - r, y, x + r, y); line(x, y - r, x + r, y); line(x, y + r, x + r, y); break; case 1: line(x - r, y, x + r, y); line(x, y - r, x - r, y); line(x, y + r, x - r, y); break; case 2: line(x, y - r, x, y + r); line(x - r, y, x, y + r); line(x + r, y, x, y + r); break; case 3: line(x, y - r, x, y + r); line(x - r, y, x, y - r); line(x + r, y, x, y - r); break; default: return 0; break; } return 1; } void printf_pad(void) { int i, j; int max = 0; int x, y; char res[20] = "res/res-1.png"; /* struct step { int y; int x; }steps[_x*_x + 1], end;*/ struct step { int y; int x; }*steps, end; steps = (struct step *)malloc((_x*_x + 1)*sizeof(struct step)); x = mx * 2 + 1; y = my * 2 + 1; initgraph(605, 605); setbkcolor(WHITE); setcolor(BLACK); setcaption("Maze"); for (j = 0; j < y; j += 2) for (i = 1; i < x - 1; i += 2) if (maze[j][i] == WALL) line(2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx); for (j = 0; j < x; j += 2) for (i = 1; i < y - 1; i += 2) if (maze[i][j] == WALL) line(2 + (j / 2) * 600.0 / mx, 2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx); for (i = 0; i<_x; i++) { for (j = 0; j<_x; j++) { if (maze[i][j] == WALL) ; else if (maze[i][j]>0) { steps[maze[i][j]].y = i; steps[maze[i][j]].x = j; if (maze[i][j]>max) max = maze[i][j]; } else if (maze[i][j] == END) { end.y = i; end.x = j; steps[max + 1].y = i; steps[max + 1].x = j; } else ; } } setcolor(RED); for (i = 1; i <= max; i++) { if (steps[i].x % 2 && steps[i].y % 2) { for (j = 0; j < 4; j++) { if (steps[i].x + direction[j].x == steps[i + 1].x&&steps[i].y + direction[j].y == steps[i + 1].y) break; } draw_arrow(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1 + (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9, j); //circle(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1+ (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9); Sleep(20); } } PIMAGE image[6], screen; screen = newimage(); getimage(screen, 0, 0, 605, 605); for (i = 0; i < 6; i++) { image[i] = newimage(); getimage(image[i], res, 0, 0); res[8] += 1; } setfont(60, 0, "宋体"); setbkmode(TRANSPARENT); settextjustify(CENTER_TEXT, CENTER_TEXT); for (i = 0; i < 4; i++) { for (j = 0; j < 6; j++) { setfont(60 + ((j == 2 || j == 5) ? 0 : 1) * 10, 0, "宋体"); outtextxy(303, 250, "SUCCESS"); putimage_withalpha(NULL, image[j], 100, 305); //putimage(100, 200, image[j], SRCINVERT); if (j == 2 || j == 5) Sleep(150); Sleep(200); //cleardevice(); putimage(0, 0, screen); } } putimage(0, 0, screen); getch(); closegraph(); return; } int move(int n) { int i; if (maze[explorer.y][explorer.x] == END) { printf_pad(); //getchar(); exit(0); } maze[explorer.y][explorer.x] = n; for (i = 0; i<4; i++) { if (can_move(explorer.y + direction[i].y, explorer.x + direction[i].x)) { explorer.y += direction[i].y; explorer.x += direction[i].x; move(n + 1); maze[explorer.y][explorer.x] = NOTWAY; explorer.y -= direction[i].y; explorer.x -= direction[i].x; } } maze[explorer.y][explorer.x] = NOTWAY; return 0; } int is_map_created() { int i, j, x, y; x = mx * 2 + 1; y = my * 2 + 1; for (i = 1; i<y - 1; i += 2) for (j = 1; j<x - 1; j += 2) if (maze[i][j] == 0) { temp.y = i; temp.x = j; return 0; } return 1; } int can_go(int x, int y) { if (x<1 || y<1 || x >= mx * 2 + 1 || y >= my * 2 + 1) return 0; else if (maze[y][x]>0) return 0; return 1; } int can_set(int x, int y) { if (x<1 || y<1 || x >= mx * 2 || y >= my * 2) return 0; else if (maze[y][x]<1) return 0; return 1; } void print_maze() { int i, j, x, y; x = mx * 2 + 1; y = my * 2 + 1; for (i = 0; i<y; i++) { for (j = 0; j<x; j++) { if (maze[i][j] == WALL) { printf("#"); } else printf(" "); } printf("\n"); } } int make_map() { int step, i, direction_temp, count = 0, d; maze[maker.y][maker.x] = sign; for (i = 0; i<4; i++) { if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y)) { count++; } } if (count == 0) return 0; step = rand() % 3 + 1; direction_temp = rand() % 4; for (i = 0; i<step; i++) { if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y)) { maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign; maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign; maker.x += 2 * direction[direction_temp].x; maker.y += 2 * direction[direction_temp].y; } else { d = rand() % 4; direction_temp = d; } } return 1; } int com_map() { int i; for (i = 0; i<4; i++) { if (can_set(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y)) { maze[maker.y + direction[i].y][maker.x + direction[i].x] = sign + 1; return 1; } } return 0; } int make_map_dps() { int step, i, direction_temp, count = 0, d; maze[maker.y][maker.x] = 1; if (maker_n == 100) { printf_pad(); getchar(); closegraph(); exit(0); } for (i = 0; i<4; i++) { if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y)) { count++; } } if (count == 0) return 0; step = rand() % 3 + 1; direction_temp = rand() % 4; for (i = 0; i<step; i++) { if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y)) { maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign; maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign; maker.x += 2 * direction[direction_temp].x; maker.y += 2 * direction[direction_temp].y; maker_step[++i_maker_step] = direction_temp + 1; maker_n++; } else { d = rand() % 4; direction_temp = d; } } return 1; } int move_back() { int i; if (i_maker_step<0 || i_maker_step >= mx*my) exit(0); i = maker_step[i_maker_step--] - 1; maker.y = maker.y - 2 * direction[i].y; maker.x = maker.x - 2 * direction[i].x; return 1; } int main() { int i, j, x, y, s, e, maker_total; int *p_temp; char str[10]; setinitmode(NULL); initgraph(400, 300); setcaption("MAZE"); inputbox_getline("请输入迷宫的大小", "请输入一个数字，输入完请回车", str, sizeof(str) / sizeof(*str)); mx = my = atoi(str); if (mx<1 || mx>200) { mx = MX; my = MY; _x = _X; _y = _Y; } else { _x = mx * 2 + 1; _y = my * 2 + 1; } maker_total = mx*my; x = mx * 2 + 1; y = my * 2 + 1; closegraph(); maker_step = (int *)calloc(mx*my, sizeof(int)); maze = (int **)calloc(y, sizeof(int *)); p_temp = (int *)calloc(x*y, sizeof(int)); for (i = 0; i<y; i++) { maze[i] = p_temp + x*i; } for (i = 0; i<y; i++) { for (j = 0; j<x; j++) { maze[i][j] = !(j % 2) || !(i % 2) || i == 0 || i == y - 1 ? WALL : 0; } } maker.y = 1; maker.x = 1; srand(time(NULL)); while (maker_n != maker_total) { while (make_map_dps()) ; move_back(); } /* while (!is_map_created()) { while (make_map()) ; sign++; maker = temp; if (sign >= 3) com_map(); } maker = temp; if (sign >= 3) com_map();*/ for (i = 0; i<y; i++) for (j = 0; j<x; j++) if (maze[i][j]>0) maze[i][j] = 0; srand(time(NULL)); s = rand() % (mx); e = rand() % (mx); explorer.x = 2 * s + 1; explorer.y = 0; maze[0][2 * s + 1] = START; maze[y - 1][2 * e + 1] = END; printf_pad(); //move(1); return 0; } |