Skip to content

4061. Minimum Queen Moves to Reach Target

DifficultyEasy

Description

There is an 8 x 8 empty chessboard with 1-indexed rows and columns.

You are given an array source = [sr, sc] representing the starting position of a queen, and an array target = [tr, tc] representing the target position.

In one move, the queen travels one or more squares along a single row, column, or diagonal, staying within the board.

Return the minimum number of moves for the queen to land exactly on target.

 

Example 1:

Input: source = [8,1], target = [1,8]

Output: 1

Explanation:

​​​​​​​​​​​​​​

A single diagonal move takes the queen straight from (8, 1) to (1, 8).

Example 2:

Input: source = [4,2], target = [1,3]

Output: 2

Explanation:

​​​​​​​

The queen moves from (4, 2) to (4, 3), then from (4, 3) to (1, 3), reaching the target in 2 moves.

Example 3:

Input: source = [1,1], target = [1,1]

Output: 0

Explanation:

The queen is already at the target position, so no moves are needed.

 

Constraints:​​​​​​​

  • source == [sr, sc]
  • target == [tr, tc]
  • 1 <= sr, sc, tr, tc <= 8

Solutions

Solution 1: Case Analysis

Thinking

The board is only \(8\times 8\), so a BFS from the source also finds the shortest path. One queen move reaches any square on the same row, column, or diagonal, and the distance can only be \(0\), \(1\), or \(2\).

When the two squares differ, move along the row to \((s_r, t_c)\) and then along the column to \((t_r, t_c)\). Two moves always arrive, and the board is empty.

If that intermediate square coincides with either end, the source and the target already share a row or a column, so one move is enough. It remains only to test equality, a shared row or column, and a shared diagonal.

The answer is \(0\) when \((s_r, s_c)\) and \((t_r, t_c)\) are the same square.

A queen moves any number of squares along one row, one column, or one diagonal. The answer is \(1\) when \(s_r=t_r\), \(s_c=t_c\), or \(|s_r-t_r|=|s_c-t_c|\).

Every remaining pair takes two moves. Go from \((s_r, s_c)\) to \((s_r, t_c)\), then from \((s_r, t_c)\) to \((t_r, t_c)\). The squares share neither a row nor a column, so the intermediate square differs from both ends. The board is empty, and both moves are legal. The answer is \(2\).

The time complexity is \(O(1)\) and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def minQueenMoves(self, source: list[int], target: list[int]) -> int:
        sr, sc = source
        tr, tc = target
        if sr == tr and sc == tc:
            return 0
        if sr == tr or sc == tc or abs(sr - tr) == abs(sc - tc):
            return 1
        return 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minQueenMoves(int[] source, int[] target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if (sr == tr && sc == tc) {
            return 0;
        }
        if (sr == tr || sc == tc || Math.abs(sr - tr) == Math.abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minQueenMoves(vector<int>& source, vector<int>& target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if (sr == tr && sc == tc) {
            return 0;
        }
        if (sr == tr || sc == tc || abs(sr - tr) == abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minQueenMoves(source []int, target []int) int {
    sr, sc := source[0], source[1]
    tr, tc := target[0], target[1]
    if sr == tr && sc == tc {
        return 0
    }
    if sr == tr || sc == tc || abs(sr-tr) == abs(sc-tc) {
        return 1
    }
    return 2
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minQueenMoves(source: number[], target: number[]): number {
    const [sr, sc] = source;
    const [tr, tc] = target;
    if (sr === tr && sc === tc) {
        return 0;
    }
    if (sr === tr || sc === tc || Math.abs(sr - tr) === Math.abs(sc - tc)) {
        return 1;
    }
    return 2;
}

Comments