Question

3001. 捕获黑皇后需要的最少移动次数

English Version

题目描述

现有一个下标从 1 开始的 8 x 8 棋盘，上面有 3 枚棋子。

给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：

• (a, b) 表示白色车的位置。
• (c, d) 表示白色象的位置。
• (e, f) 表示黑皇后的位置。

假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。

请注意：

• 车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
• 象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
• 如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
• 皇后不能移动。

 

示例 1：

输入：a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出：2
解释：将白色车先移动到 (1, 3) ，然后移动到 (2, 3) 来捕获黑皇后，共需移动 2 次。
由于起始时没有任何棋子正在攻击黑皇后，要想捕获黑皇后，移动次数不可能少于 2 次。

示例 2：

输入：a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
输出：1
解释：可以通过以下任一方式移动 1 次捕获黑皇后：
- 将白色车移动到 (5, 2) 。
- 将白色象移动到 (5, 2) 。

 

提示：

• 1 <= a, b, c, d, e, f <= 8
• 两枚棋子不会同时出现在同一个格子上。

解法

方法一

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

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;
  }
};

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;
}