题解 | #迷宫问题# HJ43

#include <stdio.h>
int map[10][10];
int migong(int row,int col,int x,int y){
      int up=0,down=0,right=0,left=0,sum=0;
      if(x<row-1&&map[x+1][y]==0){
        down=1;
      }
      if(y<col-1&&map[x][y+1]==0){
         right=1;
      }
      sum=down+right;

    while(sum==1){                   //有一个位置就做
        map[x][y]=2;                 //该 位置为必经路，设为2，方便打印
        if(down==1){x++;down=0;}        
        if(up==1){x--;up=0;}
        if(right==1){y++;right=0;}
        if(left==1){y--;left=0;}      //选择路走。
      if(x==row-1&&y==col-1){map[x][y]=2;return 1;}   //只要变换坐标，就检查到终点没。没有这个24/26会失败
      if(x<row-1&&map[x+1][y]==0){             //下一个看看左右上下四条路，来路已经被换为2了，不走回头路
        down=1; 
      }
      if(x>0&&map[x-1][y]==0){
        up=1;
      }
      if(y>0&&map[x][y-1]==0){
        left=1;
      }
      if(y<col-1&&map[x][y+1]==0){
         right=1;
      }
      sum=up+down+right+left;                 //下一个点有几个位置，
    }
    //以上总结，直线道路
    //以下为岔口和死路，终点

      if(x==row-1&&y==col-1){map[x][y]=2;return 1;}         //唯一一个死路是终点为活路
      if(sum==0){return 0; }     //死路返回信号0
      if(sum>1){                    //岔路口，调用本函数，并接受信号是否死路，按理说只有一条活路
          map[x][y]=2;
          if(down==1){
            down=migong(row,col,x+1,y);
            if(down==1){return 1;}
            else{map[x+1][y]=1;}
          }
          if(up==1)  {
            up  =migong(row,col,x-1,y);
               if(up==1){return 1;}
               else{map[x-1][y]=0;}
          }

          if(right==1){
            right=migong(row,col,x,y+1);
            if(right==1){return 1;}
            else{map[x][y+1]=1;}
            }

          if(left==1){
            left=migong(row,col,x,y-1);
            if(left==1){return 1;}
            else{map[x][y-1]=1;}
            }
      }
    return 1;
}
int main() {

    for(int i=0;i<10;i++){
         for(int j=0;j<10;j++){
             map[i][j]=1;
         }
    }
    int a, b;
    scanf("%d %d\n", &a, &b); // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 

    for(int i=0;i<a;i++){
        for(int j=0;j<b;j++){
            scanf("%d ",&map[i][j]);
        }
    }
    int flag=migong(a,b,0,0);                    //规划路线

 /*   for(int i=0;i<10;i++){                         //打印看看路线是否正确，连续的2就是正确路线
         for(int j=0;j<10;j++){
             printf("%d ",map[i][j]);
         }
         printf("\n");
    }
*/
    int i=0,j=0;
    while(map[i][j]==2&&i<a&&j<b){    //打印步骤
        map[i][j]=3;                  //这里换位三，防止回头
        printf("(%d,%d)\n",i,j);

        if(i<a-1&&map[i+1][j]==2){            
          i++;
          continue;
        }
         if(i>0&&map[i-1][j]==2){
           i--;
           continue;
        }
        if(j>0&&map[i][j-1]==2){
           j--;
           continue;
        }
        if(j<b-1&&map[i][j+1]==2){
           j++;
           continue;
        }
    }
    
    //从0，0到a-1，b-1

    
    return 0;
}