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

79愛的鼓勵 1訂閱站台

BFS是佇列的應用
也就是先進先出 DFS是堆疊 先進後出
之前文章的變數打錯`XD 請原諒我 我懶得改了
此題必須考慮棋盤的邊界問題 因為會有差別 害我吃WA

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

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
main()  
{  
 int n,m,a,b;  
 char x[3],y[3];
 while(scanf("%s %s",x,y)==2)  
   {  
    if(strcmp(x,y)==0) {printf("To get from %s to %s takes 0 knight moves.\n",x,y);continue;}
    char map[11][11]={0};
    int ansx=y[0]-'a',ansy=y[1]-'1',startx=x[0]-'a',starty=x[1]-'1';
    char queue[64][2]={0},top=0,ans;
    map[ansx][ansy]=-1;
    queue[0][0]=startx;queue[0][1]=starty;
     for(a=0;a<=top;a++)
       {
        int nn=queue[a][0],mm=queue[a][1];
        if(map[nn+2][mm+1]==-1||map[nn+2][mm-1]==-1||map[nn-1][mm+2]==-1||map[nn-1][mm-2]==-1||map[nn-2][mm+1]==-1||map[nn-2][mm-1]==-1||map[nn+1][mm-2]==-1||map[nn+1][mm+2]==-1)
         {ans=map[nn][mm]+1;break;}
        if(map[nn+2][mm+1]==0&&nn+2<8&&mm+1<8)
          {
           map[nn+2][mm+1]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn+2;queue[top][1]=mm+1;
          }
        if(map[nn+2][mm-1]==0&&nn+2<8&&mm-1>=0)
         {
           map[nn+2][mm-1]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn+2;queue[top][1]=mm-1;
          } 
        if(map[nn-1][mm+2]==0&&nn-1>=0&&mm+2<8)
          {
           map[nn-1][mm+2]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn-1;queue[top][1]=mm+2;
          }
        if(map[nn-1][mm-2]==0&&nn-1>=0&&mm-2>=0)
          {
           map[nn-1][mm-2]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn-1;queue[top][1]=mm-2;
          }
        if(map[nn-2][mm+1]==0&&nn-2>=0&&mm+1<8)
          {
           map[nn-2][mm+1]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn-2;queue[top][1]=mm+1;
          }
        if(map[nn-2][mm-1]==0&&nn-2>=0&&mm-1>=0)
          {
           map[nn-2][mm-1]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn-2;queue[top][1]=mm-1;
          }
        if(map[nn+1][mm-2]==0&&nn+1<8&&mm-2>=0)
         {
           map[nn+1][mm-2]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn+1;queue[top][1]=mm-2;
          }
        if(map[nn+1][mm+2]==0&&nn+1<8&&mm+2<8)
          {
           map[nn+1][mm+2]=map[nn][mm]+1;
           top++;
           queue[top][0]=nn+1;queue[top][1]=mm+2;
          }
       }
       printf("To get from %s to %s takes %d knight moves.\n",x,y,ans);
   }   
 return 0;  
}