Minimum Moves to Capture The Queen
Source: leetcode
Difficulty: Medium
Tags: math, enumeration

There is a **1\-indexed** `8 x 8` chessboard containing `3` pieces.


You are given `6` integers `a`, `b`, `c`, `d`, `e`, and `f` where:


- `(a, b)` denotes the position of the white rook.
- `(c, d)` denotes the position of the white bishop.
- `(e, f)` denotes the position of the black queen.


Given that you can only move the white pieces, return *the **minimum** number of moves required to capture the black queen*.


**Note** that:


- Rooks can move any number of squares either vertically or horizontally, but cannot jump over other pieces.
- Bishops can move any number of squares diagonally, but cannot jump over other pieces.
- A rook or a bishop can capture the queen if it is located in a square that they can move to.
- The queen does not move.


 


**Example 1:**


![](https://assets.leetcode.com/uploads/2023/12/21/ex1.png)

```

Input: a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
Output: 2
Explanation: We can capture the black queen in two moves by moving the white rook to (1, 3) then to (2, 3).
It is impossible to capture the black queen in less than two moves since it is not being attacked by any of the pieces at the beginning.

```

**Example 2:**


![](https://assets.leetcode.com/uploads/2023/12/21/ex2.png)

```

Input: a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
Output: 1
Explanation: We can capture the black queen in a single move by doing one of the following: 
- Move the white rook to (5, 2).
- Move the white bishop to (5, 2).

```

 


**Constraints:**


- `1 <= a, b, c, d, e, f <= 8`
- No two pieces are on the same square.




C++ solution:
class Solution {
public:
    // time/space: O(1)/O(1)
    int minMovesToCaptureTheQueen(int yRook, int xRook, int yBishop, int xBishop, int yQueen, int xQueen) {
        // try to move the rook in 1 step
        if (xRook == xQueen) {
            // check if the bishop is block the vertical way
            if ((xRook == xBishop) && 
                (((yRook < yBishop) && (yBishop < yQueen)) ||
                ((yQueen < yBishop) && (yBishop < yRook)))) {}
            else return 1;
        }
        if (yRook == yQueen) {
            // check if the bishop is block the horizontal way
            if ((yRook == yBishop) && 
                (((xRook < xBishop) && (xBishop < xQueen)) ||
                ((xQueen < xBishop) && (xBishop < xRook)))) {}
            else return 1;
        }
        
        // try to move the bishop in 1 step
        int dxQ2B = xQueen - xBishop;
        int dyQ2B = yQueen - yBishop;
        if (abs(dxQ2B) == abs(dyQ2B)) {
            int dxR2B = xRook - xBishop;
            int dyR2B = yRook - yBishop;
            // check if the rock is block the bishop's way
            if (isSameSlope(dxQ2B, dyQ2B, dxR2B, dyR2B) &&
                isSameDirection(dxQ2B, dyQ2B, dxR2B, dyR2B) &&
                (abs(dxQ2B) > abs(dxR2B)) &&
                (abs(dyQ2B) > abs(dyR2B))) {}
            else return 1;
        }
        
        return 2;
    }
private:
    bool isSameSlope(int dx1, int dy1, int dx2, int dy2) {
        return ((dx1 * dy2) == (dx2 * dy1));
    }
    bool isSameDirection(int dx1, int dy1, int dx2, int dy2) {
        if ((dx1 * dx2) < 0) return false;
        if ((dy1 * dy2) < 0) return false;
        return true;
    }
};

Go solution:
func minMovesToCaptureTheQueen(rx, ry int, bx, by int, qx, qy int) int {
	if canBishopCaptureQueen(bx, by, qx, qy, rx, ry) || canRookCaptureQueen(rx, ry, qx, qy, bx, by) {
		return 1
	}

	return 2
}

func canBishopCaptureQueen(bx, by, qx, qy, rx, ry int) bool {
	return (onUpwardDiagonal(bx, by, qx, qy) && (!onUpwardDiagonal(bx, by, rx, ry) || !isInTheMiddle(bx, rx, qx))) || (onDownwardDiagonal(bx, by, qx, qy) && (!onDownwardDiagonal(bx, by, rx, ry) || !isInTheMiddle(bx, rx, qx)))
}

func canRookCaptureQueen(rx, ry, qx, qy, bx, by int) bool {
	return (onHorizontalLine(rx, qx) && (!onHorizontalLine(rx, bx) || !isInTheMiddle(ry, by, qy))) || (onVerticalLine(ry, qy) && (!onVerticalLine(ry, by) || !isInTheMiddle(rx, bx, qx)))
}

func onUpwardDiagonal(x1, y1, x2, y2 int) bool {
	return y1-x1 == y2-x2
}

func onDownwardDiagonal(x1, y1, x2, y2 int) bool {
	return y1+x1 == y2+x2
}

func onHorizontalLine(x1, x2 int) bool {
	return x1 == x2
}

func onVerticalLine(y1, y2 int) bool {
	return y1 == y2
}

func isInTheMiddle(start, mayBeMiddle, end int) bool {
	if end < start {
		start, end = end, start
	}

	return start < mayBeMiddle && mayBeMiddle < end
}

Java solution:
class Solution {
    public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        if(a == e || b == f) {
            if(a == e && a == c && ((d-b) * (d-f) < 0)) return 2;
            if(b == f && b == d && ((c-a) * (c-e) < 0)) return 2;
            return 1;
        }
        if(Math.abs(c - e) == Math.abs(d - f)) {
            if(Math.abs(c - a) == Math.abs(d - b) && Math.abs(e - a) == Math.abs(f - b) && ((b-f) * (b-d) < 0))  return 2;
            return 1;
        }
        return 2;
    }
}

JavaScript solution:
/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @param {number} d
 * @param {number} e
 * @param {number} f
 * @return {number}
 */
var minMovesToCaptureTheQueen = function(a, b, c, d, e, f) {
    if (a === e) {
        if (!(a === c && (b - d) * (d - f) > 0)) {
            return 1
        }
    }

    if (b === f) {
        if (!(b === d && (a - c) * (c - e) > 0)) {
            return 1
        }
    }

    const diffQueen = e - f, diffBishop = c - d
    if (diffQueen === diffBishop) {
        const diffRook = a - b
        if (diffRook !== diffQueen) return 1
        if ((c - a) * (a - e) < 0)  return 1
    }

    const sumQueen = e + f, sumBishop = c + d
    if (sumQueen === sumBishop) {
        const sumRook = a + b
        if (sumRook !== sumQueen) return 1
        if ((c - a) * (a - e) < 0)  return 1
    }

    return 2
};

Python solution:
class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        rook, bishop, queen = (a, b), (c, d), (e, f)

        if rook[0] == queen[0] or rook[1] == queen[1]:
            if not (bishop[0] == rook[0] or bishop[1] == rook[1]):
                return 1

            if (min(rook[0], queen[0]) <= bishop[0] <= max(rook[0], queen[0])) and (min(rook[1], queen[1]) <= bishop[1] <= max(rook[1], queen[1])):
                return 2

            return 1
        
        if abs(bishop[0] - queen[0]) == abs(bishop[1] - queen[1]):
            # First check if rook is on the diagonal of bishop and queen
            if not (abs(bishop[0] - rook[0]) == abs(bishop[1] - rook[1])):
                return 1
            
            # Check if rook lies between bishop and queen
            if (min(bishop[0], queen[0]) <= rook[0] <= max(bishop[0], queen[0])) and (min(bishop[1], queen[1]) <= rook[1] <= max(bishop[1], queen[1])):
                return 2

            return 1
        
        return 2

Ruby solution:
def min_moves_to_capture_the_queen(a, b, c, d, e, f)
    # Check if rook can capture in one move
    if a == e
        # Same row
        if c == a
            min_col = [b, f].min
            max_col = [b, f].max
            if d >= min_col && d <= max_col
                # Blocked by bishop
            else
                return 1
            end
        else
            return 1
        end
    elsif b == f
        # Same column
        if d == b
            min_row = [a, e].min
            max_row = [a, e].max
            if c >= min_row && c <= max_row
                # Blocked by bishop
            else
                return 1
            end
        else
            return 1
        end
    end

    # Check if bishop can capture in one move
    if (c - e).abs == (d - f).abs
        if (a - c).abs != (b - d).abs
            return 1
        else
            dxq = e - c
            dyq = f - d
            dxr = a - c
            dyr = b - d

            same_sign_x = (dxq * dxr) >= 0
            same_sign_y = (dyq * dyr) >= 0

            if same_sign_x && same_sign_y
                if dxq.abs > dxr.abs && dyq.abs > dyr.abs
                    # Blocked by rook
                else
                    return 1
                end
            else
                return 1
            end
        end
    end

    2
end