摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : BFS擴張

從起點BFS擴張,若到終點則輸出,若沒辦法到達則輸出0

/***********************************************************/

#include<stdlib.h>
#include<stdio.h>
main()
{
   int t,n,m;
   scanf("%d",&t);
   while(t--)
       {
          scanf("%d %d",&n,&m);
          int map[101][101]={0},sx,sy,ex,ey,a,b,c;
          char s[101];
          scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
          for(a=0;a<n;a++)
             {
                scanf("%s",s);
                for(b=0;b<m;b++)
                   if(s[b]=='1') map[a][b]=-1;
             }
          int queue[10000][2]={0},top=0,find=0;
          queue[0][0]=sx-1;queue[0][1]=sy-1;
          for(a=0;a<=top;a++)
             {
               int xx=queue[a][0],yy=queue[a][1];
               if(xx==ex-1&&yy==ey-1) {find=1;break;}
               if(map[xx+1][yy]==0&&xx+1<n)
                  {
                     map[xx+1][yy]=map[xx][yy]+1;
                     top++;
                     queue[top][0]=xx+1;queue[top][1]=yy;
                  }
               if(map[xx-1][yy]==0&&xx-1>=0)
                  {
                     map[xx-1][yy]=map[xx][yy]+1;
                     top++;
                     queue[top][0]=xx-1;queue[top][1]=yy;
                  }
               if(map[xx][yy+1]==0&&yy+1<m)
                  {
                     map[xx][yy+1]=map[xx][yy]+1;
                     top++;
                     queue[top][0]=xx;queue[top][1]=yy+1;
                  }
               if(map[xx][yy-1]==0&&yy-1>=0)
                  {
                     map[xx][yy-1]=map[xx][yy]+1;
                     top++;
                     queue[top][0]=xx;queue[top][1]=yy-1;
                  }
             }
          if(find==1)
          printf("%d\n",map[ex-1][ey-1]+1);
          else printf("0\n");
         /* for(a=0;a<n;a++)
             {
                for(b=0;b<m;b++)
                   printf("%3d ",map[a][b]);
                printf("\n");
             }*/
       }
   return 0;
}
/*
2
5 6 3 1 3 4
000000
011101
000010
011000
000010

*/