/* 程序名称： 迷宫求解 * 所用编译器： 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;}
#include <graphics.h>#include <stdlib.h>#include <stdio.h>#include <conio.h>#include <dos.h>#define N 20/*迷宫的大小，可改变*/int oldmap[N][N];/*递归用的数组,用全局变量节约时间*/int yes=0;/*yes是判断是否找到路的标志,1找到，0没找到*/int way[100][2],wayn=0;/*way数组是显示路线用的,wayn是统计走了几个格子*/void Init(void);/*图形初始化*/void Close(void);/*图形关闭*/void DrawPeople(int *x,int *y,int n);/*画人工探索物图*/void PeopleFind(int (*x)[N]);/*人工探索*/void WayCopy(int (*x)[N],int (*y)[N]);/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/int FindWay(int (*x)[N],int i,int j);/*自动探索函数*/void MapRand(int (*x)[N]);/*随机生成迷宫函数*/void PrMap(int (*x)[N]);/*输出迷宫图函数*/void Result(void);/*输出结果处理*/void Find(void);/*成功处理*/void NotFind(void);/*失败处理*/void main(void)/*主函数*/{ int map[N][N]; /*迷宫数组*/ char ch; clrscr(); printf("\n Please select hand(1) else auto\n");/*选择探索方式*/ scanf("%c",&ch); Init(); /*初始化*/ MapRand(map);/*生成迷宫*/ PrMap(map);/*显示迷宫图*/ if(ch=='1') PeopleFind(map);/*人工探索*/ else FindWay(map,1,1);/*系统自动从下标1,1的地方开始探索*/ Result();/*输出结果*/ Close();}void Init(void)/*图形初始化*/{ int gd=DETECT,gm; initgraph(&gd,&gm,"c:\\tc");}void DrawPeople(int *x,int *y,int n)/*画人工控制图*/{/*如果将以下两句注释掉，则显示人工走过的路径，*/ setfillstyle(SOLID_FILL,WHITE); /*设置白色实体填充样式*/ bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);/*恢复原通路*/ switch(n)/*判断x,y的变化，8个方向的变化*/ { case 1: (*x)--;break; /*上*/ case 2: (*x)--;(*y)++;break ;/*右上*/ case 3: (*y)++;break; /*右*/ case 4: (*x)++;(*y)++;break; /*右下*/ case 5: (*x)++;break; /*下*/ case 6: (*x)++;(*y)--;break; /*左下*/ case 7: (*y)--;break; /*左*/ case 8: (*x)--;(*y)--;break; /*左上*/ } setfillstyle(SOLID_FILL,RED);/*新位置显示探索物*/ bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);}void PeopleFind(int (*map)[N])/*人工手动查找*/{ int x,y; char c=0;/*接收按键的变量*/ x=y=1;/*人工查找的初始位置*/ setcolor(11); line(500,200,550,200); outtextxy(570,197,"d"); line(500,200,450,200); outtextxy(430,197,"a"); line(500,200,500,150); outtextxy(497,130,"w"); line(500,200,500,250); outtextxy(497,270,"x"); line(500,200,450,150); outtextxy(445,130,"q"); line(500,200,550,150); outtextxy(550,130,"e"); line(500,200,450,250); outtextxy(445,270,"z"); line(500,200,550,250); outtextxy(550,270,"c");/*以上是画8个方向的控制介绍*/ setcolor(YELLOW); outtextxy(420,290,"Press 'Enter' to end");/*压回车键结束*/ setfillstyle(SOLID_FILL,RED); bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置显示*/ while(c!=13)/*如果按下的不是回车键*/ { c=getch();/*接收字符后开始各个方向的探索*/ if(c=='w'&&map[x-1][y]!=1) DrawPeople(&x,&y,1);/*上*/ else if(c=='e'&&map[x-1][y+1]!=1) DrawPeople(&x,&y,2);/*右上*/ else if(c=='d'&&map[x][y+1]!=1) DrawPeople(&x,&y,3);/*右*/ else if(c=='c'&&map[x+1][y+1]!=1) DrawPeople(&x,&y,4);/*右下*/ else if(c=='x'&&map[x+1][y]!=1) DrawPeople(&x,&y,5);/*下*/ else if(c=='z'&&map[x+1][y-1]!=1) DrawPeople(&x,&y,6); /*左下*/ else if(c=='a'&&map[x][y-1]!=1) DrawPeople(&x,&y,7); /*左*/ else if(c=='q'&&map[x-1][y-1]!=1) DrawPeople(&x,&y,8); /*左上*/ } setfillstyle(SOLID_FILL,WHITE); /*消去红色探索物，恢复原迷宫图*/ bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6); if(x==N-2&&y==N-2)/*人工控制找成功的话*/ yes=1; /*如果成功标志为1*/}void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */{ int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) oldmap[i][j]=map[i][j];}int FindWay(int (*map)[N],int i,int j)/*递归找路*/{ if(i==N-2&&j==N-2)/*走到出口*/ { yes=1;/*标志为1,表示成功*/ return; } map[i][j]=1;/*走过的地方变为1*/ WayCopy(oldmap,map); /*拷贝迷宫图*/ if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/ { FindWay(oldmap,i+1,j+1); if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/ { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/ { FindWay(oldmap,i+1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/ { FindWay(oldmap,i,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/ { FindWay(oldmap,i-1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/ { FindWay(oldmap,i-1,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/ { FindWay(oldmap,i+1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/ { FindWay(oldmap,i,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/ { FindWay(oldmap,i-1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } return;}void MapRand(int (*map)[N])/*开始的随机迷宫图*/{ int i,j; cleardevice();/*清屏*/ randomize(); /*随机数发生器*/ for(i=0;i<N;i++) { for(j=0;j<N;j++) { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/ map[i][j]=1; else if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/ map[i][j]=0; else map[i][j]=random(2);/*其它的随机生成0或1*/ } }}void PrMap(int (*map)[N])/*输出迷宫图*/{ int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) if(map[i][j]==0) { setfillstyle(SOLID_FILL,WHITE);/*白色为可走的路*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6); } else { setfillstyle(SOLID_FILL,BLUE);/*蓝色为墙壁*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6); }}void Find(void)/*找到通路*/{ int i; setfillstyle(SOLID_FILL,RED);/*红色输出走的具体路线*/ wayn--; for(i=wayn;i>=0;i--) { bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+ way[i][1]*15+6,50+way[i][0]*15+6); sleep(1);/*控制显示时间*/ } bar(100+(N-2)*15-6,50+(N-2)*15-6,100+ (N-2)*15+6,50+(N-2)*15+6); /*在目标点标红色*/ setcolor(GREEN); settextstyle(0,0,2);/*设置字体大小*/ outtextxy(130,400,"Find a way!");}void NotFind(void)/*没找到通路*/{ setcolor(GREEN); settextstyle(0,0,2);/*设置字体大小*/ outtextxy(130,400,"Not find a way!");}void Result(void)/*结果处理*/{ if(yes)/*如果找到*/ Find(); else/*没找到路*/ NotFind(); getch();}void Close(void)/*图形关闭*/{ closegraph();}
引用第1楼fan于2006-09-08 23:09发表的:我才入gate，只看的懂一点点。那些图形的是不是需要另外看些书学勒？我们那本 谭浩强的c语言貌似讲的很少。。。
引用第6楼minpayne于2006-09-09 13:50发表的:有兴趣参加ACM不
引用第11楼iriver_man于2006-09-10 22:58发表的:强人,怎么都喜欢在tc下写程序.
