Welcome to Subscribe On Youtube
4061. Minimum Queen Moves to Reach Target
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)$.
-
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; } } -
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; } }; -
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 -
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 } -
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; }