1197.Minimum-Knight-Moves

1197. Minimum Knight Moves

题目地址

https://leetcode.com/problems/minimum-knight-moves/

题目描述

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y].  It is guaranteed the answer exists.

Example 1:
Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Constraints:
|x| + |y| <= 300

代码

Approach #1 BFS with pruning

Time: O(N) && Space: O(N)

class Solution {
  private final int[][] DIRECTIONS = new int[][] {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
  public int minKnightMoves(int x, int y) {
    // 四个象限方向步数是一样的
        x = Math.abs(x);
    y = Math.abs(y);

    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[] {0, 0});

    Set<String> visited = new HashSet<>();
    visited.add("0,0");

    int result = 0;
    while (!queue.isEmpty()) {
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        int[] cur = queue.remove();
        int curX = cur[0];
        int curY = cur[1];
        if (curX == x && curY == y) {
          return result;
        }

        for (int[] d: DIRECTIONS) {
          int newX = curX + d[0];
          int newY = curY + d[1];
          // If you remove this condition newX >= -1 && newY >= -1) this solution would give TLE.
          if (!visited.contains(newX + "," + newY) && newX >= -1 && newY >= -1) {
            queue.add(new int[] {newX, newY});
            visited.add(newX + "," + newY);
          }
        }
      }
      result++;
    }
    return -1;
  }
}

Approach #2 DFS

class Solution {
  public int minKnightMoves(int x, int y) {
    Map<String, Integer> map = new HashMap<>();
    // base case
    map.put("0,0", 0);
    map.put("1,0", 3);
    map.put("1,1", 2);
    map.put("2,0", 2);
    return dfs(x, y, map);
  }

  private int dfs(int x, int y, Map<String, Integer> map) {
    // Sysmetrical of axis
    x = Math.abs(x);
    y = Math.abs(y);
    // Sysmetrical of diagonal
    if (x < y) {
      int temp = x;
      x = y;
      y = temp;
    }

    String s = x + "," + y;
    if (map.containsKey(s))        return map.get(s);
    int temp = Math.min(dfs(x-2, y-1, map),
                       dfs(x-1, y-2, map)) + 1;
    map.put(s, temp);
    return temp;
  }
}