题解 | #迷宫问题#

#include <math.h>
#include <stdio.h>
struct hl{
    int h;
    int l;
    int s;
    int x;
    int z;
    int y;
};
int dfs(struct hl *luxian,int a,int b,int o)
{
     if((luxian[o]).h==a-1&&(luxian[o]).l==b-1)return 1; 
     if (
        luxian[o].s>0&&
        dfs(luxian,a,b,luxian[o].s))return 1;
     if (        luxian[o].x>0&&
dfs(luxian,a,b,luxian[o].x))return 1;
     if (        luxian[o].z>0&&
dfs(luxian,a,b,luxian[o].z))return 1;
     if (        luxian[o].y>0&&
dfs(luxian,a,b,luxian[o].y))return 1;
return 0;
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);// 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
    
    int mi[a][b],t=0;
    for(int i=0;i<a*b;i++)
    {scanf("%d",&mi[i/b][i%b]);
    if(mi[i/b][i%b]==0)t++;
    }
    struct hl luxian[t];
    for(int i=0;i<t;i++)
    {luxian[i].s=-1;
    luxian[i].x=-1;
    luxian[i].z=-1;luxian[i].y=-1;
    }
    int zhan[200],jin=1,chu=0;
    int jian=1;
    zhan[0]=0;luxian[0].h=0;luxian[0].l=0;
    mi[0][0]=1;
    while(jin!=chu)//广度遍历建立多叉树
    {
        if(luxian[chu].h>0&&mi[luxian[chu].h-1][luxian[chu].l]==0)
        {
        luxian[chu].s=jian;
        luxian[jian].h=luxian[chu].h-1;
        luxian[jian].l=luxian[chu].l;
        zhan[jin++]=jian;
        jian++;
        mi[luxian[chu].h-1][luxian[chu].l]=1;}
        else luxian[chu].s=-1;
        if(luxian[chu].h<a-1&&mi[luxian[chu].h+1][luxian[chu].l]==0){
        luxian[chu].x=jian;
        luxian[jian].h=luxian[chu].h+1;
        luxian[jian].l=luxian[chu].l;
        zhan[jin++]=jian;
        jian++;
        mi[luxian[chu].h+1][luxian[chu].l]=1;}
        else luxian[chu].x=-1;
        if(luxian[chu].l>0&&mi[luxian[chu].h][luxian[chu].l-1]==0){
        luxian[chu].z=jian;
        luxian[jian].l=luxian[chu].l-1;
        luxian[jian].h=luxian[chu].h;
        zhan[jin++]=jian;jian++;
        mi[luxian[chu].h][luxian[chu].l-1]=1;}
        else luxian[chu].z=-1;
        if(luxian[chu].l<b-1&&mi[luxian[chu].h][luxian[chu].l+1]==0){
        luxian[chu].y=jian;
        luxian[jian].h=luxian[chu].h;
        luxian[jian].l=luxian[chu].l+1;
        zhan[jin++]=jian;jian++;
        mi[luxian[chu].h][luxian[chu].l+1]=1;}
        else luxian[chu].y=-1;
        chu++;
    }
   // printf("%d",a);
    //dfs(luxian,a,b,0));
  for(int i=0;i<t;i++)
  if(dfs(luxian,a, b, i))
printf("(%d,%d)\n",luxian[i].h,luxian[i].l);
    return 0;
}