Skip to content

1197. Minimum Knight Moves

  • Time: $O(xy)$
  • Space: $O(xy)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int minKnightMoves(int x, int y) {
    return dp(abs(x), abs(y));
  }

 private:
  struct pairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };

  unordered_map<pair<int, int>, int, pairHash> memo;

  int dp(int x, int y) {
    if (x + y == 0)  // (0, 0)
      return 0;
    if (x + y == 2)  // (0, 2), (1, 1), (2, 0)
      return 2;
    if (memo.count({x, y}))
      return memo[{x, y}];

    return memo[{x, y}] = min(
      dp(abs(x - 2), abs(y - 1)),
      dp(abs(x - 1), abs(y - 2))) + 1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int minKnightMoves(int x, int y) {
    return dp(Math.abs(x), Math.abs(y));
  }

  private Map<Pair<Integer, Integer>, Integer> memo = new HashMap<>();

  private int dp(int x, int y) {
    if (x + y == 0) // (0, 0)
      return 0;
    if (x + y == 2) // (0, 2), (1, 1), (2, 0)
      return 2;
    Pair<Integer, Integer> key = new Pair<>(x, y);
    if (memo.containsKey(key))
      return memo.get(key);

    final int minMove = Math.min(
        dp(Math.abs(x - 2), Math.abs(y - 1)),
        dp(Math.abs(x - 1), Math.abs(y - 2))) + 1;
    memo.put(key, minMove);
    return minMove;
  }
}