fork download 
  1. #include <iostream>
  2. 	#include <array>
  3. 	#include <utility>
  4. 	#include <set>
  5. 	#include <map>
  6. 	#include <queue>
  7.  
  8. 	struct Point
  9. 	{
  10. 		int x;
  11. 		int y;
  12.  
  13. 		Point() : x(0), y(0) {}
  14. 		Point(int x, int y) : x(x), y(y) {}
  15. 		Point operator+(const Point& p) const
  16. 		{
  17. 			return Point(x + p.x, y + p.y);
  18. 		}
  19.  
  20. 		bool operator<(const Point& p) const
  21. 		{
  22. 			if(p.x == x)
  23. 				return p.y < y;
  24. 			return p.x < x;
  25. 		}
  26.  
  27. 		bool operator==(const Point& p) const
  28. 		{
  29. 			return p.x == x && p.y == y;
  30. 		}
  31. 	};
  32.  
  33. 	std::array<Point, 8> movements {
  34. 		Point(-1,-2), Point(1,-2), Point(-1, 2), Point(1, 2),
  35. 		Point(-2,-1), Point(2,-1), Point(-2, 1), Point(2, 1)
  36. 	};
  37.  
  38. 	int main()
  39. 	{
  40. 		Point start;
  41. 		Point destination;
  42. 		std::cin >> destination.x >> destination.y;
  43. 		std::map<std::pair<Point, Point>, int> dist;
  44. 		std::queue<Point> queue;
  45. 		std::set<Point> visited;
  46.  
  47. 		queue.push(start);
  48. 		visited.insert(start);
  49. 		while(!queue.empty())
  50. 		{
  51. 			auto current = queue.front();
  52. 			if(current == destination)
  53. 				break;
  54. 			queue.pop();
  55.  
  56. 			for(auto& move: movements)
  57. 			{
  58. 				auto neighbor = current + move;
  59. 				if(visited.find(neighbor) != visited.end())
  60. 					continue;
  61. 				visited.insert(neighbor);
  62. 				queue.push(neighbor);
  63. 				dist[std::make_pair(start, neighbor)] = dist[std::make_pair(start, current)] + 1;
  64. 			}
  65. 		}
  66. 		std::cout << dist[std::make_pair(start, destination)] << std::endl;
  67. 	}
Success #stdin #stdout 0s 16072KB
comments ()
stdin 
3 7
stdout 
4
https://ideone.com/mO903O
language:
C++14 (gcc 8.3)
created:
7 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!