fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FR0(i,N) for(i=0;i<(N);i++)
  4. #define FR1(i,N) for(i=1;i<=(N);i++)
  5. #define FRN(i,k,N) for(i=k;i<(N);i++)
  6. #define pf printf
  7. #define db double
  8. #define max3(a,b,c) max(max(a,b),c)
  9. #define min3(a,b,c) min(min(a,b),c)
  10. #define sci(n) scanf("%d",&n)
  11. #define scl(n) scanf("%lld",&n)
  12. #define scf(n) scanf("%f",&n)
  13. #define scd(n) scanf("%lf",&n)
  14. #define scs(s) scanf("%s",&s)
  15. #define scll(n) scanf("%%I64d",&n)
  16. #define PI acos(-1.0)
  17. #define LL long long
  18. #define MX 1000005
  19. #define MOD 1000000007
  20. typedef long long int ll;
  21. bool status[1100002];
  22. //int start_row,start_col,end_row,end_col;
  23. int cost[100][100];
  24. int check[100][100];
  25. queue<int>Q;
  26. int dr[]={+2,-2,+2,-2,+1,-1,+1,-1};
  27. int dc[]={+1,+1,-1,-1,+2,+2,-2,-2};
  28. //int dr[]= {-2,-2,+2,+2,+1,-1,+1,-1};
  29. //int dc[]= {+1,-1,+1,-1,-2,-2,+2,+2};
  30. //queue<int>Q;
  31. int start_row,start_col,end_row,end_col;
  32. void BFS(int r,int c)
  33. {
  34.     check[r][c]=1;
  35.     cost[r][c]=0;
  36.     Q.push(r);
  37.     Q.push(c);
  38.     while(!Q.empty())
  39.     {
  40.         int u=Q.front();
  41.         Q.pop();
  42.         int v=Q.front();
  43.         Q.pop();
  44.         for(int i=0;i<8;i++)
  45.         {
  46.             int row=dr[i]+u;
  47.             int col=dc[i]+v;
  48.             if(((row>=0 && row<8)&&(col>=0 && col<8)) &&(check[row][col]==0))
  49.             {
  50.                 check[row][col]=1;
  51.                 cost[row][col]=cost[u][v]+1;
  52.                 Q.push(row);
  53.                 Q.push(col);
  54.             }
  55.         }
  56.     }
  57. }
  58. int main()
  59. {
  60.     string s1,s2;
  61.     while(cin>>s1>>s2)
  62.     {
  63.       start_row=s1[0]-96;
  64.       start_col=s1[1]-'0';
  65.       end_row=s2[0]-96;
  66.       end_col=s2[1]-'0';
  67.       memset(cost,0,sizeof(cost));
  68.       memset(check,0,sizeof(check));
  69.       BFS(start_row-1,start_col-1);
  70.       cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<cost[end_row-1][end_col-1]<<" knight moves."<<endl;
  71.     }
  72. }
  73.  
Success #stdin #stdout 0s 4620KB
comments (?)
stdin
copy 
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
stdout
copy 
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
https://ideone.com/qiPaXX
language:
C++14 (clang 8.0)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!