迷宫问题讨论---(递归)

递归的本质就是使用Stack，但是，递归的可读性无疑更好

1，迷宫（maze)的表示

使用二维数组。将整个迷宫看作一张地图，这张地图有m*n个小格子个构成。如果，是墙壁则此出对应的坐标为1，反之为0。----这是一个极好的模型！在许多程序中都可以使用。（比如俄罗斯方块)

2，寻路方式

    本质上就是从上下左右四个方向寻找0，如果是0则继续，反之推出。

下面这段代码是网上bird网友所作,由于我拿来和堆栈的比较,所以将其列在下面:

typedef int STATUS;

 

void InitMaze(int maze[][10])
{
 maze[1][1]=1; maze[1][2]=1; maze[1][4]=1;
 maze[1][5]=1; maze[1][6]=1; maze[1][8]=1;
 maze[2][1]=1; maze[2][2]=1; maze[2][4]=1;
 maze[2][5]=1; maze[2][6]=1; maze[2][8]=1;
 maze[3][1]=1; maze[3][2]=1; maze[3][3]=1;
 maze[3][4]=1; maze[3][7]=1; maze[3][8]=1;
 maze[4][1]=1; maze[4][5]=1; maze[4][6]=1;
 maze[4][7]=1; maze[4][8]=1;
 maze[5][1]=1; maze[5][2]=1; maze[5][3]=1;
 maze[5][5]=1; maze[5][6]=1; maze[5][7]=1;
 maze[5][8]=1;
 maze[6][1]=1; maze[6][3]=1; maze[6][4]=1;
 maze[6][5]=1;   maze[6][7]=1; maze[6][8]=1;
 maze[7][1]=1; maze[7][5]=1; maze[7][8]=1;
 maze[8][2]=1; maze[8][3]=1; maze[8][4]=1;
 maze[8][5]=1; maze[8][6]=1; maze[8][7]=1;
 maze[8][8]=1;
}

 

void PrintMaze(int maze[][10])
{
 int i,j;
 printf("\n");
 for(i=0;i<10;i++)
 {
  for(j=0;j<10;j++)
  {
   printf("%d ",maze[i][j]);
  }
  printf("\n");
 }
}

 

void footPrint(int maze[][10], int posX, int posY)
{
 maze[posX][posY]=0;
}

 

void printPos(int posX, int posY)
{
 printf("(%d, %d) ", posX, posY);
}

 

STATUS  Go(int maze[][10], int entranceX, int entranceY, int exitX, int exitY)
{
 if(entranceX==exitX && entranceY==exitY)
  return 1;
 if(maze[entranceX][entranceY]==0)
  return 0;

 

 footPrint(maze, entranceX, entranceY);
 if( Go(maze,entranceX+1,entranceY,exitX,exitY) ){
  printPos(entranceX, entranceY);
  return 1;
 }
 if( Go(maze,entranceX,entranceY+1,exitX,exitY) ){
  printPos(entranceX, entranceY);
  return 1;
 }
 if( Go(maze,entranceX-1,entranceY,exitX,exitY) ){
  printPos(entranceX, entranceY);
  return 1;
 }
 if( Go(maze,entranceX,entranceY-1,exitX,exitY) ){
  printPos(entranceX, entranceY);
  return 1;
 }
 return 0;
}

 

void main()
{
 int maze[10][10]={0};
 int entranceX=1, entranceY=1;
 int exitX=8, exitY=8;
 InitMaze(maze);
 PrintMaze(maze);
 if( !Go(maze,entranceX,entranceY,exitX,exitY) )
  printf("Sorry, no solution.");
}

 

 

本文地址：http://com.8s8s.com/it/it28727.htm