maze.txt

一个算法问题包括

 



#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("\n");
      } 
}

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("\n"); 
    }  
}

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)\n");
      output(rear);
      find=1; 
     }  
   
   }
  front++;
  }
 if(!find)
 printf("There is no path!\n");
}

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.\n",M,N);
 printf("Input your maze[][](the number you input must be 1 or 0):\n");/*input the data of the maze*/
 input(maze);
 printf("input completely.\n");
 while(maze[1][1]==1||maze[M][N]==1||check(maze)==0)    /*check whether the data inputed is right .*/
   {                                                    /*If the data is wrong,please input again.*/
    printf("Warning:maze[][] you input is wrong!\n");
    printf("Maze[1][1] and maze[M][N] must both equal 0.\n");
    printf("Every item of maze[][]must be 1 or 0.\n\n");
    printf("Input your maze[][] again:\n");
    input(maze);
    printf("input completely.\n");  
   }
 printf("Press any key to display the path.\n");
 getch(); 
 inimove(move);
 path();
 printf("press ENTER to end the program:\n");
 scanf("%c",&ch);
}