fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int stp[9][9];
  5.  
  6. string a, b;
  7.  
  8. struct Node{
  9. 	int x,y;
  10. };
  11. int dx[8]={-2,-2,-1,-1,1,1,2,2};
  12. int dy[8]={-1,1,-2,2,-2,2,-1,1};
  13.  
  14. deque<Node> dq;
  15.  
  16. int main() {
  17. 	while( cin>>a>>b ){
  18. 		for(int i=1;i<=8;i++){
  19. 			for(int j=1;j<=8;j++)
  20. 				stp[i][j]=-1;
  21. 		}
  22. 		// start
  23. 		int x1=a[0]-'a'+1;
  24. 		int y1=a[1]-'0';
  25. 		// end
  26. 		int x2=b[0]-'a'+1;
  27. 		int y2=b[1]-'0';
  28.  
  29. 		stp[x1][y1]=0;
  30.  
  31. 		Node S;
  32. 		S.x=x1; S.y=y1;
  33. 		dq.push_back(S);
  34. 		if( x1==x2 and y1==y2 ){
  35. 			cout<<"To get from "<<a<<" to "<<b<<" takes "<<0<<" knight moves."<<'\n';
  36. 			continue;
  37. 		}	
  38.  
  39. 		while( !dq.empty() ){
  40. 			Node now=dq.front();
  41. 			dq.pop_front();
  42.  
  43. 			for(int i=0;i<8;i++){
  44. 				int nxt_x=now.x+dx[i];
  45. 				int nxt_y=now.y+dy[i];
  46. 				if( 1<=nxt_x and nxt_x<=8 and 1<=nxt_y and nxt_y<=8 ){
  47. 					if( stp[nxt_x][nxt_y]!=-1 )
  48. 						continue;
  49. 					stp[nxt_x][nxt_y]=stp[now.x][now.y]+1;
  50. 					Node nxt;
  51. 					nxt.x=nxt_x; nxt.y=nxt_y;
  52. 					dq.push_back(nxt);
  53. 					if( nxt_x==x2 and nxt_y==y2 )
  54. 						cout<<"To get from "<<a<<" to "<<b<<" takes "<<stp[nxt_x][nxt_y]<<" knight moves."<<'\n';
  55. 				}
  56. 			}
  57. 		}		
  58.  
  59. 	}
  60. }
Success #stdin #stdout 0.01s 5300KB
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/zATnfd
c117. 00439 - Knight Moves -- UVa439
language:
C++ (gcc 8.3)
created:
1 year 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!