C++での最小の騎士の動き

座標が-無限大から+無限大までの無限のチェス盤があり、正方形[0、0]に騎士がいるとします。騎士は、以下に示すように、8つの可能な動きをすることができます。それぞれの動きは、基本方向に2マス、次に直交方向に1マスです。

騎士を正方形[x、y]に移動するために必要な最小ステップ数を見つける必要があります。答えが存在することが保証されています。

したがって、入力がx=5およびy=5の場合、出力は4になります。これは[0,0]→[2,1]→[4,2]→[3,4]→[のようになります。 5,5]

これを解決するには、次の手順に従います-

• マップを定義するm

• Solve（）というメソッドを定義します。これにはxとyが必要です

• x + y =0の場合は0を返し、x + y =2の場合は2を返します

• （x、y）を使用してペアtempを作成します

• mにtempのペアがある場合は、m [temp]

  を返します。

• return m [temp]：=min ofsolve（| x-1 |、| y-2 |））、[solve（| x-2 |、| y-1 |））+ 1]

• mainメソッドから、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

出力

4