maze.h

经典迷宫问题求解

typedef struct
{int m,n;
 char arr[100][100];
}MazeType;

void InitMaze(MazeType &maze,int a[][10],int row,int col)
{
 maze.m=row;maze.n=col;
 int i,j;
 for(i=0;i<100;i++)
   for(j=0;j<100;j++)
   maze.arr[i][j]=1;
 for(i=1;i<=maze.m;i++)
	 for(j=1;j<=maze.n;j++)
		 maze.arr[i][j]=a[i-1][j-1];
 }


Status Pass(MazeType maze,PosType curpos)
{if(maze.arr[curpos.r][curpos.c]==0)
   return 1;
 else return 0;
}

void FootPrint(MazeType &maze,PosType curpos)
{maze.arr[curpos.r][curpos.c]='*';}

Status Same(PosType curpos,PosType end)
{if(curpos.r==end.r&&curpos.c==end.c)
       return 1;
 else return 0;
}

PosType NextPos(PosType &curpos,directiveType di)
{switch(di)
{case 1:
	curpos.c=curpos.c+1;break;
  case 2:
    curpos.r=curpos.r+1;break;
  case 3:
    curpos.c=curpos.c-1;break;
  case 4:
	curpos.r=curpos.r-1;break;
  }
 return curpos;
}

void MarkPrint(MazeType &maze,PosType es)
 {maze.arr[es.r][es.c]='@';}


void Back(MazeType &maze)
{	for(int i=1;i<maze.m+1;i++)
	{for(int j=1;j<maze.n+1;j++)
       if(maze.arr[i][j]=='#')
	  maze.arr[i][j]=1;
	   else
		   if(maze.arr[i][j]=='*'||maze.arr[i][j]=='@')
	  maze.arr[i][j]=0;
	}
}

Status MazePath(MazeType &maze,PosType start,PosType end)
{ElemType e;PosType curpos;Stack s;
  InitStack(s);curpos=start;
  int curstep=1;int found=FALSE;
 Back(maze);
  do{
	 if(Pass(maze,curpos))
	 {
		 FootPrint(maze,curpos);
	 e.step=curstep;
	 e.seat.r=curpos.r;
	 e.seat.c=curpos.c;
	 e.di=1;
	  Push(s,e);
	  if(Same(curpos,end)) found=TRUE;
      else{

		  curpos=NextPos(curpos,1);
		  curstep++;
	  }
	 }
	 else
	 {

		 if(!StackEmpty(s)){
			 Pop(s,e);
			 while(e.di==4&&!StackEmpty(s))
			 {MarkPrint(maze,e.seat);
			   Pop(s,e);
			   curstep--;
			 }
			 if(e.di<4){
				 e.di++;Push(s,e);
				 curpos=NextPos(e.seat,e.di);
			 }
		 }
		 }
 }while(!StackEmpty(s)&&!found);
for(int i=1;i<maze.m+1;i++)
  {for(int j=1;j<maze.n+1;j++)
	  if(maze.arr[i][j]==1)
	  maze.arr[i][j]='#';}
 return found;
}