迷宫求解问题.zip

#include<malloc.h> #include<stdio.h> #include<conio.h> #define M 6 /*规定迷宫的行数*/ #define N 4 /*规定迷宫的列数*/ int i=0; typedef struct shuju{ int data; int flag; /*判断这个位置是否被走过,使其产生记忆效果*/ }SHU; typedef struct maze{ int c; int flag; int direct; int x; int y; struct maze *next; }MG; MG *top,*p; MG * pop(int bb,int xx,int yy,SHU t[M][N]) /*入栈操作*/ {int i2,j2; i++; p=(MG *)malloc(sizeof(MG)); p->c=bb; p->flag=1; p->direct=4; p->x=xx; p->y=yy; if(i==1) {top=p; top->next=NULL; } else {p->next=top; top=p; } clrscr(); for(i2=0;i2<M;i2++) {printf("\n"); for(j2=0;j2<N;j2++) if(t[i2][j2].data==8) {textcolor(YELLOW); cprintf("%3d",t[i2][j2].data); } else {textcolor(WHITE); cprintf("%3d",t[i2][j2].data); } } for(i2=0;i2<80;i2++) /*时间延迟*/ delay(1000); } int way(int x1,int y1,SHU s[M][N]) /*寻找路径函数*/ { int x,y,f=0; int i1,j1; while(top!=NULL) /*以下是在四个方向上进行判断 通就入栈，不通就进行下个方向的 判断，如果四个方向都不通，就出栈*/ if(top->flag==1) {x=top->x; y=top->y; if(x==x1&&y==y1) { f=1; break; } /*判断右方向*/ if(top->direct==4) {top->direct--; if(0<=y+1&&y+1<N) /*判断数组的下标是否超过了规定的界限*/ if(s[x][y+1].data==0&&s[x][y+1].flag==0) pop(s[x][y+1].data=8,x,y+1,s); } else if(top->direct==3) /*判断下方向*/ {top->direct--; if(0<=x+1&&x+1<M) if(s[x+1][y].data==0&&s[x+1][y].flag==0) pop(s[x+1][y].data=8,x+1,y,s); } else if(top->direct==2) /*判断左方向*/ {top->direct--; if(0<=y-1&&y-1<N) if(s[x][y-1].data==0&&s[x][y-1].flag==0) pop(s[x][y-1].data=8,x,y-1,s); } else if(top->direct==1) /*判断上方向*/ {top->direct--; top->flag=0; if(0<=x-1&&x-1<M) if(s[x-1][y].data==0&&s[x-1][y].flag==0) pop(s[x-1][y].data=8,x-1,y,s); } } else {s[top->x][top->y].data=0; s[top->x][top->y].flag=1; top=top->next; clrscr(); for(i1=0;i1<M;i1++) {printf("\n"); for(j1=0;j1<N;j1++) if(s[i1][j1].data==8) {textcolor(YELLOW); cprintf("%3d",s[i1][j1].data); } else {textcolor(WHITE); cprintf("%3d",s[i1][j1].data); } } for(i1=0;i1<80;i1++) /*产生时间延迟,不同的CPU产生的延迟效果不一样*/ delay(1000); } return f; } main() {SHU s[M][N]; int x,y,x1,y1; int i1,j1,i,j,F; for(i1=0;i1<M;i1++) for(j1=0;j1<N;j1++) /*迷宫图面，用一个数字表示*/ s[i1][j1].data=8; for(i1=0;i1<M;i1++) {printf("\n"); for(j1=0;j1<N;j1++) printf("%3d",s[i1][j1].data); /*打印迷宫最原始的界面，用数字8表示每个 } 位置*/ } printf("\nplese drink a migong --0 is yes --1 is no\n"); for(i1=0;i1<M;i1++) for(j1=0;j1<N;j1++) {printf("\nb[%d][%d]=",i1,j1); scanf("%d",&s[i1][j1].data); /*绘制迷宫，0代表通，1代表不通*/ s[i1][j1].flag=0; clrscr(); for(i=0;i<M;i++) {printf("\n"); for(j=0;j<N;j++) if(s[i][j].data==0) {textcolor(YELLOW); cprintf("%3d",s[i][j].data); } else if(s[i][j].data==1) {textcolor(RED); cprintf("%3d",s[i][j].data); } else {textcolor(WHITE); cprintf("%3d",s[i][j].data); } } } textcolor(WHITE); printf("\nmi gong tu is :"); for(i1=0;i1<M;i1++) {printf("\n"); for(j1=0;j1<N;j1++) printf("%3d",s[i1][j1].data); } printf("\nplease input the ru kou zuo biao(x&y)\n for example input:0 0\ninput:"); /*输入迷宫的入口坐标(X,Y)*/ scanf("%d %d",&x,&y); printf("please input the chu kou zuo biao(x1&y1)\n for example input:3 3\ninput:"); /*输入迷宫的出口坐标（X1，Y1)*/ scanf("%d %d",&x1,&y1); printf("press any key to continue:"); getch(); while(s[x][y].data!=0) /*判断是否有入口位置*/ {printf("Not find ru kou\n"); printf("please input again: "); scanf("%d %d",x,y); } pop(s[x][y].data=8,x,y,s); F=way(x1,y1,s); /*路径进行判断函数*/ textcolor(WHITE); if(F==0) cprintf("\r\nben mi gong mei you jie!\n"); else cprintf("\r\nben mi gong you way:\n"); cprintf("\r\npress any key to quit.\n"); getch(); }