/* 程序名称： 迷宫求解 * 所用编译器： Turboc 2.0 * 作者：Killua * 学校：电子科技大学 * 专业班级：04级软件工程2班 * 版本：1.0 *//*----------------------头文件--------------------*/#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<time.h>#include<alloc.h>#include<dos.h>#include<graphics.h>/*------------------------------------------------*//* ----------定义程序中用到的常量-----------------*/#define STACKMAX 100 /*栈元素的最大存储结构*/#define BGI#define size 30 /* 方块的边长 */#define TRUE 1#define FALSE 0#define ROWS 10 /* 迷宫的行数 */#define COLS 10 /* 迷宫的列数 */#define EAST 1 /* 方向东 */#define SOUTH 2 /* 方向南 */#define WEST 3 /* 方向西 */#define NORTH 4 /* 方向北 *//*-------------------------------------------------*//*-------------------全局常量----------------------*/ /* 迷宫中墙的数据 ，每两个一组 * 比如第一组(3,1)表示在board[3][1]处有墙 */ int board_data[] = {3, 1, 3, 2, 7, 1, 7, 2, 5, 3, 6, 3, 2 ,4, 3, 4, 4, 4, 4, 5, 2, 6, 2, 7, 3, 7, 4, 7, 1, 8, 6, 6, 6, 7, 7, 7}; char Board[COLS][ROWS]; /* 存储迷宫数据的矩阵 *//*-------------------------------------------------*//*------------------定义一系列结构体---------------*/typedef int Direction; /* mouse移动的方向 */typedef struct Position /* mouse位置坐标的结构体 */{ int x; int y;}Position;/* 存入栈的元素的结构体 */typedef struct elemType{ Position pos; /* mouse的位置 */ Direction direction; /* 下一个移动的方向 */}elemType;typedef struct stack/*定义栈结构*/{ elemType elem[STACKMAX];/*存储栈元素的数组*/ int top;/*栈顶元素的下标*/}stack;/*栈的初始化*/void Init_stack(stack* s){ s->top = 0;}/*压入元素入栈*/int push(stack* s,elemType x){ if( s->top == STACKMAX ) return FALSE; else { s->top = s->top + 1; s->elem[s->top] = x; return TRUE; }}/*元素出栈*/elemType pop(stack* s){ s->top = s->top - 1; return s->elem[s->top+1];}/* 栈判空函数 */int Stack_Empty(stack *s){ if (s->top == 0) return TRUE; else return FALSE;}/*--------------------------------------------------------*//*-----------------------函数声明--------------------------*/void Init_graph(void); /* 初始化为图形模式 */void Draw_Border(void); /* 画迷宫的边框 */void Draw_Text(void); /* 写文字 */void Init_Board(void); /* 初始化迷宫数据 */void Draw_Rect(int x, int y); /* 画迷宫墙的方块 */void Draw_Board(void); /* 画迷宫 */void Init(void); /* 将所有的初始化包含其中 */int Pass(Position curpos); /* 判断mouse能不能在当前位置通过*/void FootPrint(Position curpos); /* mouse走过的位置置1 */Position NextPos(Position curpos, Direction direction); /* 取得mouse要走的下一个位置 */void Draw_Mouse(int x, int y); /* 画mouse */int MazePath(Position start, Position end); /* 若迷宫中存在从入口到出口的的路径，就让栈存储次路径 *//*---------------------------------------------------------*//*------------------------函数定义-----------------------------------------*//*-----------------进入图形模式函数Init_graph-------------*/void Init_graph(void){ int gdriver=DETECT,gmode; registerbgidriver(EGAVGA_driver); initgraph(&gdriver, &gmode, "c:\\turboc2");}/*--------------------------------------------------------*//*------------------画迷宫边框的函数--------------------------*/void Draw_Border(void){ int space = 5; setfillstyle(XHATCH_FILL, YELLOW); bar(290, 90-space-1, 590, 90-1); bar(290-space-1, 90-space-1, 290-1, 390+space+1); bar(590+1, 90-space-1, 590+space+1, 390+space+1); bar(290, 390+1, 590, 390+1+space);}/*-----------------------写文字-----------------------------*/void Draw_Text(void){ setcolor(GREEN); outtextxy(50, 120, "Program: MazePath"); outtextxy(50, 140, "Version: 1.0"); outtextxy(50, 160, "Author: Liu Chao"); outtextxy(50, 180, "QQ: 53408770"); outtextxy(50, 200, "Email: [email]kangtalc@163.com[/email]"); outtextxy(50, 220, "Software School of UESTC");}/*----------------------------------------------------------*//*---------------------初始化迷宫的数据--------------------*/void Init_Board(void){ /* 如果迷宫(i, j)位置有墙，则置Board[i][j]为‘#’ * 否则为0 */ int array_size; int i , j; for (i = 0; i < 10; i++) { for (j = 0; j < 10; j++) { if (i == 0 || j == 0 || i == 9 || j == 9) Board[i][j] = '#'; else Board[i][j] = 0; } } array_size = sizeof(board_data)/sizeof(int); for (i = 0; i < array_size; i += 2) Board[board_data[i]][board_data[i+1]] = '#';}/*---------------------------------------------------------*//*----------------------画方块的函数----------------------*/void Draw_Rect(int x, int y){ int realx, realy; realx = x * size + 290; realy = y * size + 90; bar(realx + 1, realy + 1, realx + size - 1, realy + size - 1);}/*------------------------------------------------------------*//*-----------------------画迷宫障碍物的函数-------------------*/void Draw_Board(void){ int i, j; for (i = 0; i < COLS; i++) { for (j = 0; j < ROWS; j++) { if (Board[i][j] == '#') { setfillstyle(SOLID_FILL, LIGHTRED); Draw_Rect(i, j); } } }}/*-------------------------------------------------------------*//*---------------将上面的各个函数封装为一个函数做初始化--------*/void Init(void){ Init_graph(); Init_Board(); Draw_Border(); Draw_Text(); Draw_Board();}/*-------------------------------------------------------------*//*------------------判断mouse在当前位置能不能通过--------------*/int Pass(Position curpos){ if (Board[curpos.x][curpos.y] == 1 || Board[curpos.x][curpos.y] == '#') return FALSE; else return TRUE;}/*-------------------------------------------------------------*//*-----------------------记录mouse走过的痕迹------------------*/void FootPrint(Position curpos){ Board[curpos.x][curpos.y] = 1;}/*------------------------------------------------------------*//*----------------取得mouse可能移动到的下一个位置-------------*/Position NextPos(Position curpos, Direction direction){ switch(direction) { case EAST: curpos.x++; break; case SOUTH: curpos.y++; break; case WEST: curpos.x--; break; case NORTH: curpos.y--; } return curpos;}/*---------------------------------------------------------------*//*-----------------------画mouse---------------------------------*/void Draw_Mouse(int x, int y){ int realx, realy; realx = x * size + 290; realy = y * size + 90; bar(realx + 3, realy + 3, realx + size - 3, realy + size - 3);}/*----------------------------------------------------------------*//*---------------------------时间延迟函数-----------------------*/void time_delay() { double i=0; for(i=0;i<18390000;) i++;}/*--------------------------------------------------------------*//*--------------------------求从START到END的一条路径------------*//* 若迷宫MAZE中存在从入口START到出口END的通道 * 则求得一条存放在栈中（从栈底到栈顶） * 并返回TRUE，否则返回FALSE */int MazePath(Position start, Position end){ stack s; elemType e; Position curpos = start; /* 设定当前位置为入口位置 */ Position last_pos = curpos; /* 记录上一个位置 */ Init_stack(&s); /* 初始化栈 */ do { if (Pass(curpos)) /* 如果 mouse能在当前位置通过，即是未曾走过的通道块*/ { FootPrint(curpos); /* 清除上一个方块，画当前方块 */ setfillstyle(SOLID_FILL, BLACK); Draw_Mouse(last_pos.x, last_pos.y); setfillstyle(SOLID_FILL, LIGHTBLUE); Draw_Mouse(curpos.x, curpos.y); time_delay(); last_pos = curpos;/*将当前方块设为上一个方块*/ /* 加入路径 */ e.pos = curpos; e.direction = EAST; push(&s, e);/* 压入栈 */ /* 如果到了出口 */ if (curpos.x == end.x && curpos.y == end.y) { setfillstyle(SOLID_FILL, LIGHTBLUE); Draw_Mouse(curpos.x, curpos.y); return TRUE; } /*下一个位置是当前位置的东邻*/ curpos = NextPos(curpos, EAST); } else /* 不能在当前位置通过 */ { if (!Stack_Empty(&s)) { { /* 出栈，并且从画mouse */ e = pop(&s); setfillstyle(SOLID_FILL, BLACK); Draw_Mouse(last_pos.x, last_pos.y); setfillstyle(SOLID_FILL, LIGHTBLUE); Draw_Mouse(e.pos.x, e.pos.y); time_delay(); last_pos = e.pos; } /* 找到一个可通的相邻块，并且从画mouse */ while ( e.direction == NORTH && !Stack_Empty(&s)) { e = pop(&s); setfillstyle(SOLID_FILL, BLACK); Draw_Mouse(last_pos.x, last_pos.y); setfillstyle(SOLID_FILL, LIGHTBLUE); Draw_Mouse(e.pos.x, e.pos.y); time_delay(); last_pos = e.pos; } if (e.direction < NORTH) { e.direction++; /* 探索下一个方向 */ push(&s, e); curpos = NextPos(e.pos, e.direction); /* 设定当前位置为该新方向上的相邻块 */ } } } }while(!Stack_Empty(&s));}/* 主函数 */int main(){ /* 设定能否找到路径 */ int status = FALSE; /* 设定入口和出口 */ Position start, end; start.x = 1, start.y = 1; end.x = 8, end.y = 8; Init(); status = MazePath(start, end); if(status) { setcolor(BLUE); outtextxy(50, 300, "The mouse can find the Path!"); getch(); } else { setcolor(BLUE); outtextxy(50, 300, "The Path is wrong"); getch(); } closegraph(); return 0;}
