算法-迷宫问题（递归）

迷宫问题：之前只用栈来实现，现在使用递归来实现。blog.csdn.net/feixiaoxing/article/details/6894981 

#define N 6

int MG[N][N]; // 迷宫数组，0表示墙壁，1表示联通

int G_Value[N][N];  //用来记录是否走过， 走过是 #，没走过是原始值

int check_pos_valid(int x,int y)

{

if((x<0||x>N-1)||(y<0||y>N-1))//出界

{

return 0;

}

if (MG[x][y] == 0)//墙

{

return 0;

}

if (G_Value[x][y] == '#')//已经走过

{

return 0;

}

return 1;//可以使用

}

void printPath()

{

      for (int i = 0; i< N; i++ )

      {

              for (int j = 0 ; j< N;j++ )

              {

                      if(G_Value[i][j] == '#')

                     {

                      printf("#");//将走过的路线打印出来

                     }

                    else

                    {

                           printf(" ");

                    }

                   }

                  printf("\n");

           }

       printf("\n");

}

void FindPath(int x,int y)

{

if(check_pos_valid(x,y))

{

if(MG[x][y] == 2)//找到终点

{

         G_Value[x][y] = '#';//已经走过

         printPath(); //走过的路线打印出来

           G_Value[x][y] = 0;    //终点这里仍然可以继续走

           return;

}

G_Value[x][y] = '#'; // 走过 mark

FindPath(x-1, y);    //四个方向 分别是 上下左右

FindPath(x, y+1);

FindPath(x+1, y);

FindPath(x, y-1);

G_Value[x][y] = 0;   //如果四个方向都没有找到终点   这个position的寻找过程结束，回到上一个position，这个重新当做未走过

}

}