fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> moves;
  6. int dx[] = {2,1,-1,-2,-2,-1,1,2};
  7. int dy[] = {1,2,2,1,-1,-2,-2,-1};
  8. int visited[9][9];
  9. void run(int x1, int y1, int x2, int y2, int d){
  10.     if(x1<1||y1<1||x1>8||y1>8) {
  11.         //cout<<"return from out of box"<<endl;
  12.         return;
  13.     }
  14.     else if(x1==x2&&y1==y2){
  15.         moves.push_back(d);
  16.         //cout<<"Pushed here"<<endl;
  17.         return;
  18.     }
  19.     else{
  20. /*
  21.         cout<<"RUN Called--> x1: "<<x1<<" y1 :"<<y1<<endl;
  22.         cout<<"d: "<<d<<endl;
  23.         cout<<"vis: "<<visited[x1][y1]<<endl;
  24. */
  25.         if(visited[x1][y1]>d){
  26.             visited[x1][y1]=d;
  27.             for(int i=0; i<8; i++){
  28.                 //cout<<"x1: "<<x1<<" y1 :"<<y1<<endl;
  29.                 //cout<<"d: "<<d<<endl;
  30.                 //cout<<"vis: "<<visited[x1][y1]<<endl;
  31.                 //cout<<"dx: "<<dx[i]<<" dy: "<<dy[i]<<endl;
  32.                 run(x1+dx[i], y1+dy[i], x2, y2, d+1);
  33.             }
  34.         }
  35.     }
  36. }
  37. int main(){
  38.     string s1;
  39.     string s2;
  40.     while(cin>>s1>>s2){
  41.         for(int j=0; j<=8; j++){
  42.             for(int k=0; k<=8; k++){
  43.                 visited[j][k] = 999999999;
  44.             }
  45.         }
  46.         moves.clear();
  47.         int x1= s1[0]-'a'+1;
  48.         int y1= s1[1]-'0';
  49.         int x2= s2[0] -'a'+1;
  50.         int y2= s2[1]-'0';
  51.         //cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
  52.         run(x1, y1, x2, y2, 0);
  53.         int minM= 99999999;
  54.         int len= moves.size();
  55.         for(int i=0; i<len; i++){
  56.             if(moves[i]<minM) minM=moves[i];
  57.         }
  58.         cout<<"To get from "<<s1<<" to "<<s2<<" takes "<<minM<<" knight moves."<<endl;
  59.     }
  60. }
  61.  
Success #stdin #stdout 0s 15240KB
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/WdZu5o
language:
C++14 (gcc 8.3)
created:
4 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!