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

79愛的鼓勵 1訂閱站台

作法: BFS

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

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n;
 char x[101];
 while(scanf("%d",&n)==1)
     {
       int a,b,c,d;
       int map[102][102]={0};
       for(a=0;a<n;a++)
        {
          scanf("%s",x);
           for(b=0,c=1;b<n;b++,c++)
              map[a+1][c]=x[b];
        } 
       int max=0;
       for(a=1;a<=n;a++)
           for(b=1;b<=n;b++)
               if(map[a][b]=='1')
                   {
                      int queue[10001][2]={0},top=0,appear[102][102]={0},ans;
                      queue[0][0]=a;queue[0][1]=b;
                      for(c=0;c<=top;c++)
                         {
                           int x=queue[c][0],y=queue[c][1];
                           if(map[x][y]=='3') {ans=appear[x][y];break;}
                            if(map[x+1][y]!=0&&appear[x+1][y]==0)
                               {
                                  top++;
                                  queue[top][0]=x+1;
                                  queue[top][1]=y;
                                  appear[x+1][y]=appear[x][y]+1;
                               }
                           if(map[x][y+1]!=0&&appear[x][y+1]==0)
                               {
                                  top++;
                                  queue[top][0]=x;
                                  queue[top][1]=y+1;
                                  appear[x][y+1]=appear[x][y]+1;
                               }
                           if(map[x-1][y]!=0&&appear[x-1][y]==0)
                               {
                                  top++;
                                  queue[top][0]=x-1;
                                  queue[top][1]=y;
                                  appear[x-1][y]=appear[x][y]+1;
                               }
                           if(map[x][y-1]!=0&&appear[x][y-1]==0)
                               {
                                  top++;
                                  queue[top][0]=x;
                                  queue[top][1]=y-1;
                                  appear[x][y-1]=appear[x][y]+1;
                               }
                         }
                      if(ans>max) max=ans;
                   }
        printf("%d\n",max);
     }
 return 0;
}