fork download
copy 
  1. # include <iostream>
  2. # include <string>
  3. # include <cstdlib>
  4. # include <cstdio>
  5. # include <limits>
  6. # include <map>
  7. # include <queue>
  8. using namespace std;
  9. struct Node
  10. {
  11.     int X, Y;
  12. 	Node (int x = 0, int y = 0) {X = x; Y = y;}
  13. 	bool operator < (const Node & node) const
  14. 	{
  15. 		if (X == node.X)
  16. 		{
  17. 			return (Y < node.Y);
  18. 		}
  19. 		return (X < node.X);
  20. 	}
  21. };
  22. map <Node, int> Distances;
  23. queue <Node> Queue;
  24. Node Start, End;
  25. void Update (Node node, Node node1)
  26. {
  27. 	if (Distances.find (node1) == Distances.end())
  28. 	{
  29. 		Distances [node1] = Distances [node] + 1;
  30. 		if (node1.X != End.X || node1.Y != End.Y)
  31. 			Queue.push (node1);
  32. 	}
  33. 	else
  34. 	{
  35. 		if (Distances [node] + 1 < Distances[node1])
  36. 		{
  37. 			Distances [node1] = Distances [node] + 1;
  38. 			if (node1.X != End.X || node1.Y != End.Y)
  39. 				Queue.push (node1);
  40. 		}
  41. 	}
  42. }
  43. int main(int argc, char const *argv[])
  44. {
  45. 	//freopen ("439_Knight_Moves_input.txt", "r", stdin);
  46. 	//freopen ("439_Knight_Moves_output.txt", "w", stdout);
  47. 	string str1, str2;
  48. 	while (cin >> str1 >> str2)
  49. 	{
  50. 		Start.X = str1[0]-97; Start.Y = str1[1]-49;
  51. 		End.X   = str2[0]-97; End.Y   = str2[1]-49;
  52. 		Distances.clear();
  53. 		Distances [Start] = 0;
  54. 		Distances [End]   = numeric_limits <int>::max();
  55. 		if (Start.X != End.X || Start.Y != End.Y)
  56. 			Queue.push (Start);
  57. 		else
  58. 			Distances [End] = 0;
  59. 		while (Queue.empty() == false)
  60. 		{
  61. 			Node node = Queue.front();
  62. 			Queue.pop();
  63. 			//cout << "Popping " 
  64. 			if (node.X + 1 < 8 && node.Y + 2 < 8)
  65. 				Update (node, Node (node.X + 1, node.Y + 2));
  66. 			if (node.X + 2 < 8 && node.Y + 1 < 8)
  67. 				Update (node, Node (node.X + 2, node.Y + 1));
  68. 			if (node.X + 1 < 8 && node.Y - 2 >= 0)
  69. 				Update (node, Node (node.X + 1, node.Y - 2));
  70. 			if (node.X + 2 < 8 && node.Y - 1 >= 0)
  71. 				Update (node, Node (node.X + 2, node.Y - 1));
  72. 			if (node.X - 1 >= 0 && node.Y + 2 < 8)
  73. 				Update (node, Node (node.X - 1, node.Y + 2));
  74. 			if (node.X - 2 >= 0 && node.Y + 1 < 8)
  75. 				Update (node, Node (node.X - 2, node.Y + 1));
  76. 			if (node.X - 1 >= 0 && node.Y - 2 >= 0)
  77. 				Update (node, Node (node.X - 1, node.Y - 2));
  78. 			if (node.X - 2 >= 0 && node.Y - 1 >= 0)
  79. 				Update (node, Node (node.X - 2, node.Y - 1));
  80. 		}
  81. 		cout << "To get from " << str1 << " to " << str2 << " takes " << Distances [End] << " knight moves." << endl;
  82. 	}
  83. 	return 0;
  84. }
Success #stdin #stdout 0.01s 2824KB
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/ORzXcK
language:
C++ (gcc 8.3)
created:
13 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!