Welcome to Subscribe On Youtube

3001. Minimum Moves to Capture The Queen

Description

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:

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:

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.

Solutions

  • class Solution {
        private final int[] dirs1 = {-1, 0, 1, 0, -1};
        private final int[] dirs2 = {-1, 1, 1, -1, -1};
        private int e, f;
    
        public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
            this.e = e;
            this.f = f;
            return check(dirs1, a, b, c, d) || check(dirs2, c, d, a, b) ? 1 : 2;
        }
    
        private boolean check(int[] dirs, int sx, int sy, int bx, int by) {
            for (int d = 0; d < 4; ++d) {
                for (int k = 1; k < 8; ++k) {
                    int x = sx + dirs[d] * k;
                    int y = sy + dirs[d + 1] * k;
                    if (x < 1 || x > 8 || y < 1 || y > 8 || (x == bx && y == by)) {
                        break;
                    }
                    if (x == e && y == f) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
    
  • class Solution {
    public:
        int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
            int dirs[2][5] = { {-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1} };
            auto check = [&](int i, int sx, int sy, int bx, int by) {
                for (int d = 0; d < 4; ++d) {
                    for (int k = 1; k < 8; ++k) {
                        int x = sx + dirs[i][d] * k;
                        int y = sy + dirs[i][d + 1] * k;
                        if (x < 1 || x > 8 || y < 1 || y > 8 || (x == bx && y == by)) {
                            break;
                        }
                        if (x == e && y == f) {
                            return true;
                        }
                    }
                }
                return false;
            };
            return check(0, a, b, c, d) || check(1, c, d, a, b) ? 1 : 2;
        }
    };
    
  • class Solution:
        def minMovesToCaptureTheQueen(
            self, a: int, b: int, c: int, d: int, e: int, f: int
        ) -> int:
            def check(dirs, sx, sy, bx, by) -> bool:
                for dx, dy in pairwise(dirs):
                    for k in range(1, 8):
                        x = sx + dx * k
                        y = sy + dy * k
                        if not (1 <= x <= 8 and 1 <= y <= 8) or (x, y) == (bx, by):
                            break
                        if (x, y) == (e, f):
                            return True
                return False
    
            dirs1 = (-1, 0, 1, 0, -1)
            dirs2 = (-1, 1, 1, -1, -1)
            return 1 if check(dirs1, a, b, c, d) or check(dirs2, c, d, a, b) else 2
    
    
  • func minMovesToCaptureTheQueen(a int, b int, c int, d int, e int, f int) int {
    	dirs := [2][5]int{ {-1, 0, 1, 0, -1}, {-1, 1, 1, -1, -1} }
    	check := func(i, sx, sy, bx, by int) bool {
    		for d := 0; d < 4; d++ {
    			for k := 1; k < 8; k++ {
    				x := sx + dirs[i][d]*k
    				y := sy + dirs[i][d+1]*k
    				if x < 1 || x > 8 || y < 1 || y > 8 || (x == bx && y == by) {
    					break
    				}
    				if x == e && y == f {
    					return true
    				}
    			}
    		}
    		return false
    	}
    	if check(0, a, b, c, d) || check(1, c, d, a, b) {
    		return 1
    	}
    	return 2
    }
    
  • function minMovesToCaptureTheQueen(
        a: number,
        b: number,
        c: number,
        d: number,
        e: number,
        f: number,
    ): number {
        const dirs: number[][] = [
            [-1, 0, 1, 0, -1],
            [-1, 1, 1, -1, -1],
        ];
        const check = (i: number, sx: number, sy: number, bx: number, by: number): boolean => {
            for (let d = 0; d < 4; ++d) {
                for (let k = 1; k < 8; ++k) {
                    const x = sx + dirs[i][d] * k;
                    const y = sy + dirs[i][d + 1] * k;
                    if (x < 1 || x > 8 || y < 1 || y > 8) {
                        break;
                    }
                    if (x === bx && y === by) {
                        break;
                    }
                    if (x === e && y === f) {
                        return true;
                    }
                }
            }
            return false;
        };
        return check(0, a, b, c, d) || check(1, c, d, a, b) ? 1 : 2;
    }
    
    
  • impl Solution {
        pub fn min_moves_to_capture_the_queen(a: i32, b: i32, c: i32, d: i32, e: i32, f: i32) -> i32 {
            if a == e && (c != a || (d - b) * (d - f) > 0) {
                return 1;
            }
            if b == f && (d != b || (c - a) * (c - e) > 0) {
                return 1;
            }
            if c - e == d - f && (a - e != b - f || (a - c) * (a - e) > 0) {
                return 1;
            }
            if c - e == f - d && (a - e != f - b || (a - c) * (a - e) > 0) {
                return 1;
            }
            return 2;
        }
    }
    
    

All Problems

All Solutions