C++의 최소 기사 이동

-infinity에서 +infinity까지의 좌표를 가진 무한 체스판이 있고 정사각형 [0, 0]에 기사가 있다고 가정합니다. 기사는 아래와 같이 8가지 이동이 가능합니다. 각 이동은 기본 방향으로 2칸, 그 다음 직교 방향으로 1칸입니다.

C++의 최소 기사 이동

기사를 정사각형 [x, y]로 이동하는 데 필요한 최소 단계 수를 찾아야 합니다. 답은 반드시 존재합니다.

따라서 입력이 x =5 및 y =5와 같으면 출력은 4가 됩니다. 이것은 [0,0] → [2,1] → [4,2] → [3,4] → [ 5,5]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

지도 정의
solve()라는 메서드를 정의하면 x와 y가 필요합니다.
x + y =0이면 0을 반환하고 x + y =2이면 2를 반환
(x, y)
를 사용하여 쌍 온도를 만듭니다.
m에 쌍 온도가 있으면 m[temp]
를 반환합니다.
return m[temp] :=최소 solve(|x - 1|, |y - 2|)), [solve(|x - 2|, |y - 1|)) + 1]
메인 메소드에서 solve(|x|, |y|)를 호출하고 값을 반환합니다.

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   map < pair <int, int>, int > dp;
   int solve(int x, int y){
      if(x + y == 0) return 0;
      if (x + y == 2) return 2;
      pair <int, int> temp({x, y});
      if(dp.count(temp)) return dp[temp];
      return dp[temp] = min(solve(abs(x - 1), abs(y - 2)), solve(abs(x - 2), abs(y - 1))) + 1;
   }
   int minKnightMoves(int x, int y) {
      return solve(abs(x), abs(y));
   }
};
main(){
   Solution ob;
   cout << (ob.minKnightMoves(5, 5));
}

입력

5
5