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
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> mem;

  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 (const auto it = mem.find({x, y}); it != mem.cend())
      return it->second;

    return mem[{x, y}] = 1 + min(dp(abs(x - 2), abs(y - 1)),  //
                                 dp(abs(x - 1), abs(y - 2)));
  }
};

 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> mem = 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 (mem.containsKey(key))
      return mem.get(key);

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