本人寫的迷宮，不過知道這樣才能輸出所有的路徑,望各高手刺教#include<stdio.h> #include<conio.h> #define M 5 #define N 5 strUCt queue { int x; int y; int PRe; }sq[200]; int maze[M+2][N+2]; typedef struct { int dx; int dy; }moved; moved move[8]; typedef struct { int x; int y; }ROAD; ROAD road[M*N]; void inimove(moved move[]) /*initialize move[]*/ { move[0].dx=0;move[0].dy=-1; move[1].dx=1;move[1].dy=-1; move[2].dx=1;move[2].dy=0; move[3].dx=1;move[3].dy=1; move[4].dx=0;move[4].dy=1; move[5].dx=-1;move[5].dy=1; move[6].dx=-1;move[6].dy=0; move[7].dx=-1;move[7].dy=-1; } void input(int maze[M+2][N+2]) { int i,j;char ch; for(i=0;i<=M;i++) /*set the wall outside the maze*/ { maze[i][0]=1; maze[i][N+1]=1; } for(j=0;j<=N+1;j++) /*set the wall outside the maze*/ { maze[0][j]=maze[M+1][j]=1; } for(i=1;i<=M;i++) /*input the data of maze*/ for(j=1;j<=N;j++) { ch=getch(); maze[i][j]=(int)(ch-48); printf("%3d",ch-48); printf(" "); if(!(j%N)) printf(" "); } }void output(int rear) /*output the path*/ { int i,j,k; for(j=0,k=rear;(k!=0)&&(j<M*N);j++) { road[j].x=sq[k].x; road[j].y=sq[k].y; k=sq[k].pre; }
for(i=1;i<=M;i++) for(j=1;j<=N;j++) { if(maze[i][j]==-1) { for(k=0;k<M*N;k++) { if((i==road[k].x)&&(j==road[k].y)) maze[i][j]=8; /*use '8'to mark the path*/ } if(maze[i][j]==-1) maze[i][j]=0; } printf("%3d",maze[i][j]); printf(" "); if(j%N==0) printf(" "); } } void path() /* seek the path*/ { int i,j,x,y,v,front,rear,find; sq[1].x=1;sq[1].y=1;sq[1].pre=0; find=0; front=1;rear=1;maze[1][1]=-1; while(front<=rear&&!find) { x=sq[front].x; y=sq[front].y; for(v=0;v<=7;v++) { i=x+move[v].dx; j=y+move[v].dy; if(!maze[i][j]) { rear++; sq[rear].x=i; sq[rear].y=j; sq[rear].pre=front; maze[i][j]=-1; } if(i==M&&j==N) { printf("One of the pathes is:(the path is marked by 8) "); output(rear); find=1; }
} front++; } if(!find) printf("There is no path! "); }int check(int maze[M+2][N+2]) /*check whether the data inputed is right*/ { int i,j,m,n; for(i=1;i<=M;i++) for(j=1;j<=N;j++) { if((maze[i][j]!=1)&&(maze[i][j]!=0)) { return(0); } } return(1); } main() { int i,j;char ch; printf("The size of the maze is %d*%d. ",M,N); printf("Input your maze[][](the number you input must be 1 or 0): ");/*input the data of the maze*/ input(maze); printf("input completely. "); while(maze[1][1]==1maze[M][N]==1check(maze)==0) /*check whether the data inputed is right .*/ { /*If the data is wrong,please input again.*/ printf("Warning:maze[][] you input is wrong! "); printf("Maze[1][1] and maze[M][N] must both equal 0. "); printf("Every item of maze[][]must be 1 or 0. "); printf("Input your maze[][] again: "); input(maze); printf("input completely. "); } printf("Press any key to display the path. "); getch(); inimove(move); path(); printf("press ENTER to end the program: "); scanf("%c",&ch); }
