Formatted question description: https://leetcode.ca/all/1197.html

1197. Minimum Knight Moves

Level

Medium

Description

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.

Image text

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

Solution

According to the constraint, the size of the chess board is limited, so limit the chess board size to some smaller value. For example, suppose the chess board is 800 * 800, and the knight is initially at [400, 400]. The square [x, y] is adjusted to [x + 400, y + 400] accordingly.

Simply use breadth first search. A knight has at most 8 possible moves, so for each possible move, check whether the knight is still in the chess board after the move, and add the next square to the queue if it is still in the chess board. In this way, the search space can be reduced significantly.

Once the (updated) square [x, y] is reached, return the steps to reach the square, which is guaranteed to be the minimum number of steps.

class Solution {
    public int minKnightMoves(int x, int y) {
        final int COORDINATE = 400;
        x += COORDINATE;
        y += COORDINATE;
        final int WHITE = 0;
        final int GRAY = 1;
        final int BLACK = 2;
        int length = COORDINATE * 2;
        int[][] colors = new int[length][length];
        int[][] distances = new int[length][length];
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                distances[i][j] = Integer.MAX_VALUE;
        }
        colors[COORDINATE][COORDINATE] = GRAY;
        distances[COORDINATE][COORDINATE] = 0;
        queue.offer(new int[]{COORDINATE, COORDINATE});
        int[][] directions = { {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2} };
        while (!queue.isEmpty()) {
            int[] square = queue.poll();
            int row = square[0], column = square[1];
            int distance = distances[row][column];
            for (int[] direction : directions) {
                int newRow = row + direction[0], newColumn = column + direction[1];
                if (newRow >= 0 && newRow < length && newColumn >= 0 && newColumn < length && colors[newRow][newColumn] == WHITE) {
                    colors[newRow][newColumn] = GRAY;
                    distances[newRow][newColumn] = distance + 1;
                    queue.offer(new int[]{newRow, newColumn});
                }
            }
            colors[row][column] = BLACK;
            if (colors[x][y] != WHITE)
                return distances[x][y];
        }
        return -1;
    }
}

All Problems

All Solutions