fork(2) download
copy 
  1. //https://w...content-available-to-author-only...j.com/problems/NAKANJ/
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. int arr[9][9];
  6. struct node{
  7. int x;
  8. int y;
  9. int stp;
  10. };
  11.  
  12. int main(){
  13. ios_base::sync_with_stdio(false);
  14. int test;
  15. cin>>test;
  16. while(test--){
  17.     int i,j,k,n,m,l=1,r;
  18.     char ch1,ch2;
  19. memset(arr,0,sizeof(arr));
  20. struct node ini,fi,var;
  21. cin>>ch1>>ch2;
  22. i=ch1-'a'+1;
  23. j=ch2-'0';
  24. //cout<<i<<" "<<j<<"\n";
  25. ini.y=i;
  26. ini.x=j;
  27. ini.stp=0;
  28. cin>>ch1>>ch2;
  29. i=ch1-'a'+1;
  30. j=ch2-'0';
  31. //cout<<i<<" "<<j<<"\n";
  32. fi.y=i;
  33. fi.x=j;
  34. fi.stp=0;
  35. queue<node> q;
  36. q.push(ini);
  37.  arr[ini.x][ini.y]=1;
  38. while(q.size()){
  39.     ini=q.front();
  40.     q.pop();
  41. //    cout<<" bfs on "<<ini.x<<" "<<ini.y<<"\n";
  42.     if(ini.x==fi.x && ini.y==fi.y){
  43.         fi.stp=ini.stp+1;
  44.         break;
  45.     }
  46.     i=ini.x;
  47.     j=ini.y;
  48.     if( i+2>0 && i+2<10 && j+1>0 && j+1<10 && !arr[i+2][j+1]){
  49.         var.x=ini.x+2;
  50.         var.y=ini.y+1;
  51.         var.stp=ini.stp+1;
  52.         arr[i+2][j+1]=1;
  53.         q.push(var);
  54.     }
  55.     if( i+2>0 && i+2<10 && j-1>0 && j-1<10 && !arr[i+2][j-1]){
  56.         var.x=ini.x+2;
  57.         var.y=ini.y-1;
  58.         var.stp=ini.stp+1;
  59.         arr[i+2][j-1]=1;
  60.         q.push(var);
  61.     }
  62.     if( i-2>0 && i-2<10 && j+1>0 && j+1<10 && !arr[i-2][j+1]){
  63.         var.x=ini.x-2;
  64.         var.y=ini.y+1;
  65.         var.stp=ini.stp+1;
  66.         arr[i-2][j+1]=1;
  67.         q.push(var);
  68.     }
  69.     if(i-2>0 && i-2<10 && j-1>0 && j-1<10 && !arr[i-2][j-1]){
  70.         var.x=ini.x-2;
  71.         var.y=ini.y-1;
  72.         var.stp=ini.stp+1;
  73.         arr[i-2][j-1]=1;
  74.         q.push(var);
  75.     }
  76.     if( i+1>0 && i+1<10 && j+2>0 && j+2<10 && !arr[i+1][j+2]){
  77.         var.x=ini.x+1;
  78.         var.y=ini.y+2;
  79.         var.stp=ini.stp+1;
  80.         arr[i+1][j+2]=1;
  81.         q.push(var);
  82.     }
  83.     if( i+1>0 && i+1<10 && j-2>0 && j-2<10 && !arr[i+1][j-2]){
  84.         var.x=ini.x+1;
  85.         var.y=ini.y-2;
  86.         var.stp=ini.stp+1;
  87.         arr[i+1][j-2]=1;
  88.         q.push(var);
  89.     }
  90.     if( i-1>0 && i-1<10 && j+2>0 && j+2<10 && !arr[i-1][j+2]){
  91.         var.x=ini.x-1;
  92.         var.y=ini.y+2;
  93.         var.stp=ini.stp+1;
  94.         arr[i-1][j+2]=1;
  95.         q.push(var);
  96.     }
  97.     if( i-1>0 && i-1<10 && j-2>0 && j-2<10 && !arr[i-1][j-2]){
  98.         var.x=ini.x-1;
  99.         var.y=ini.y-2;
  100.         var.stp=ini.stp+1;
  101.         arr[i-1][j-2]=1;
  102.         q.push(var);
  103.     }
  104. }
  105.  
  106.    cout<<fi.stp-1<<"\n";
  107. }
  108.  
  109. return 0;
  110. }
  111.  
  112.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
a1 h8
a1 c2
h8 c3
stdout
copy 
6
1
4
https://ideone.com/AEudIO
language:
C++14 (gcc 8.3)
created:
5 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!