Skip to content

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

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)\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

Comments