本人写的迷宫，不过知道这样才能输出所有的路径,望各高手刺教
#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);
}
|
