Welcome to Subscribe On Youtube

4034. Minimum Bishop 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 bishop, and an array target = [tr, tc] representing the target position.

In one move, the bishop travels one or more squares along a single diagonal direction, staying within the board.

Return the minimum number of moves for the bishop to land exactly on target. If it can never reach target, return -1.

 

Example 1:

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

Output: 1

Explanation:

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

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

Example 2:

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

Output: 2

Explanation:

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

Example 3:

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

Output: -1

Explanation:

No matter how many diagonal moves it makes, the bishop starting at (1, 1) can never land on (3, 4). Thus, the answer is -1.

 

Constraints:​​​​​​​

  • source.length == target.length == 2
  • 1 <= sr, sc, tr, tc <= 8
  • source != target

Solutions

Solution 1: Case Analysis

Thinking

A bishop stays on diagonals, so each move changes row and column by the same amount and $(r+c)\bmod 2$ is invariant. Opposite colours are unreachable; no search is required.

On the same colour, one move suffices if the squares already share a diagonal; otherwise any two same-colour squares on an $8\times 8$ board have a common intermediate, so the distance is $2$.

The case analysis yields only $-1$, $1$, or $2$, in constant time.

A bishop only moves along diagonals, and each move changes the row and the column by the same amount, so $(r + c) \bmod 2$ never changes. In other words, the bishop can only stand on squares of the same color as its starting square. If $(sr + sc)$ and $(tr + tc)$ have different parities, the bishop can never reach the target, so we return $-1$.

Otherwise, if the source and the target lie on the same diagonal, i.e., $|sr - tr| = |sc - tc|$, a single move is enough, so we return $1$.

In all remaining cases, the two squares share the same color but are not on a common diagonal. Since $\textit{source} \neq \textit{target}$ is guaranteed and any two same-colored squares on an $8 \times 8$ board can be joined through some intermediate square, the answer is $2$.

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

  • class Solution {
    public int minBishopMoves(int[] source, int[] target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if ((sr + sc) % 2 != (tr + tc) % 2) {
            return -1;
        }
        if (Math.abs(sr - tr) == Math.abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
}


  • class Solution {
public:
    int minBishopMoves(vector<int>& source, vector<int>& target) {
        int sr = source[0], sc = source[1];
        int tr = target[0], tc = target[1];
        if ((sr + sc) % 2 != (tr + tc) % 2) {
            return -1;
        }
        if (abs(sr - tr) == abs(sc - tc)) {
            return 1;
        }
        return 2;
    }
};


  • class Solution:
    def minBishopMoves(self, source: List[int], target: List[int]) -> int:
        sr, sc = source
        tr, tc = target
        if (sr + sc) % 2 != (tr + tc) % 2:
            return -1
        if abs(sr - tr) == abs(sc - tc):
            return 1
        return 2


  • func minBishopMoves(source []int, target []int) int {
	sr, sc := source[0], source[1]
	tr, tc := target[0], target[1]
	if (sr+sc)%2 != (tr+tc)%2 {
		return -1
	}
	if abs(sr-tr) == abs(sc-tc) {
		return 1
	}
	return 2
}

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


  • function minBishopMoves(source: number[], target: number[]): number {
    const [sr, sc] = source;
    const [tr, tc] = target;
    if ((sr + sc) % 2 !== (tr + tc) % 2) {
        return -1;
    }
    if (Math.abs(sr - tr) === Math.abs(sc - tc)) {
        return 1;
    }
    return 2;
}

All Problems

All Solutions