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 を返します。これは [1,1] や [2,0]、[0,2] のようなマスが、単純に近づくだけでは到達できず一度遠ざかる必要があるためで、特別な基底ケースとなります。
• (x, y) のペア temp を作成します。
• m に temp がすでに存在する場合は、キャッシュされた値 m[temp] を返します。
• そうでなければ、solve(|x − 1|, |y − 2|) と solve(|x − 2|, |y − 1|) の小さい方に 1 を加えた値を m[temp] に保存して返します。
• main 関数からは solve(|x|, |y|) を呼び出し、その結果を答えとして返します。座標は絶対値を取ることで第1象限に正規化でき、対称性を利用して計算量を削減できます。

メモ化により同じ座標の再計算が避けられるため、計算量はおよそ O(|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