# 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)

```java
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

```java
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;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/graph-search/1197.minimum-knight-moves.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.