🌟欢迎来到 我的博客 —— 探索技术的无限可能！
2.N 皇后 II
题目链接：52. N 皇后 II
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 9
题解：
方法：回溯 递归
class Solution { private int ans; public int totalNQueens(int n) { boolean[] col = new boolean[n]; boolean[] diag1 = new boolean[n * 2 - 1]; boolean[] diag2 = new boolean[n * 2 - 1]; dfs(0, col, diag1, diag2); return ans; } private void dfs(int r, boolean[] col, boolean[] diag1, boolean[] diag2) { int n = col.length; if (r == n) { ans++; // 找到一个合法方案 return; } for (int c = 0; c < n; c++) { int rc = r - c + n - 1; if (!col[c] && !diag1[r + c] && !diag2[rc]) { col[c] = diag1[r + c] = diag2[rc] = true; dfs(r + 1, col, diag1, diag2); col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场 } } } }
3.检查棋盘方格颜色是否相同
题目链接：3274. 检查棋盘方格颜色是否相同
给你两个字符串 coordinate1 和 coordinate2，代表 8 x 8 国际象棋棋盘上的两个方格的坐标。
以下是棋盘的参考图。
如果这两个方格颜色相同，返回 true，否则返回 false。
坐标总是表示有效的棋盘方格。坐标的格式总是先字母（表示列），再数字（表示行）。
示例 1：
输入： coordinate1 = “a1”, coordinate2 = “c3”
输出： true
解释：
两个方格均为黑色。
示例 2：
输入： coordinate1 = “a1”, coordinate2 = “h3”
输出： false
解释：
方格 “a1” 是黑色，而 “h3” 是白色。
提示：
coordinate1.length == coordinate2.length == 2
‘a’ <= coordinate1[0], coordinate2[0] <= ‘h’
‘1’ <= coordinate1[1], coordinate2[1] <= ‘8’
题解：
方法：位运算 数学
class Solution { public boolean checkTwoChessboards(String s, String t) { int a = (s.charAt(0) + s.charAt(1)) % 2; int b = (t.charAt(0) + t.charAt(1)) % 2; return a == b; } }
4.棋盘上有效移动组合的数目
题目链接：2056. 棋盘上有效移动组合的数目
有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [ri, ci] 表示第 i 个棋子现在在棋盘上的位置为 (ri, ci) ，棋盘下标从 1 开始。
每个棋子的移动中，首先选择移动的 方向 ，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：
车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1) 或者 (r, c-1) 移动。
后可以 水平竖直或者斜对角 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1)，(r, c-1)，(r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
你必须同时 移动 棋盘上的每一个棋子。移动组合 包含所有棋子的 移动 。每一秒，每个棋子都沿着它们选择的方向往前移动 一步 ，直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。
请你返回 有效 移动组合的数目。
注意：
初始时，不会有两个棋子 在 同一个位置 。
有可能在一个移动组合中，有棋子不移动。
如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 交换位置 。
示例 1:
输入：pieces = [“rook”], positions = [[1,1]]
输出：15
解释：上图展示了棋子所有可能的移动。
示例 2：
输入：pieces = [“queen”], positions = [[1,1]]
输出：22
解释：上图展示了棋子所有可能的移动。
示例 3:
输入：pieces = [“bishop”], positions = [[4,3]]
输出：12
解释：上图展示了棋子所有可能的移动。
示例 4:
输入：pieces = [“rook”,“rook”], positions = [[1,1],[8,8]]
输出：223
解释：每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。
但是，有两个是不有效的移动组合：
- 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。
示例 5：
输入：pieces = [“queen”,“bishop”], positions = [[5,7],[3,4]]
输出：281
解释：总共有 12 * 24 = 288 种移动组合。
但是，有一些不有效的移动组合：
- 如果后停在 (6, 7) ，它会阻挡象到达 (6, 7) 或者 (7, 8) 。
- 如果后停在 (5, 6) ，它会阻挡象到达 (5, 6) ，(6, 7) 或者 (7, 8) 。
- 如果象停在 (5, 2) ，它会阻挡后到达 (5, 2) 或者 (5, 1) 。
在 288 个移动组合当中，281 个是有效的。
提示：
n == pieces.length
n == positions.length
1 <= n <= 4
pieces 只包含字符串 “rook” ，“queen” 和 “bishop” 。
棋盘上最多只有一个后。
1 <= ri, ci <= 8
每一个 positions[i] 互不相同。
题解：
方法：回溯
class Solution { // 每种棋子的移动方向 private static final Map<Character, int[][]> PIECE_DIRS = Map.of( 'r', new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, // 车 'b', new int[][]{{1, 1}, {-1, 1}, {-1, -1}, {1, -1}}, // 象 'q', new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}} // 皇后 ); public int countCombinations(String[] pieces, int[][] positions) { int n = pieces.length; // 预处理所有合法移动 Move[][] allMoves = new Move[n][]; for (int i = 0; i < n; i++) { allMoves[i] = generateMoves(positions[i][0], positions[i][1], PIECE_DIRS.get(pieces[i].charAt(0))); } Move[] path = new Move[n]; // 注意 path 的长度是固定的 return dfs(0, n, allMoves, path); } // 起点 (x0,y0)，移动方向 (dx,dy)，移动次数 step private record Move(int x0, int y0, int dx, int dy, int step) { } // 计算位于 (x0,y0) 的棋子在 dirs 这些方向上的所有合法移动 private Move[] generateMoves(int x0, int y0, int[][] dirs) { final int SIZE = 8; List<Move> moves = new ArrayList<>(); moves.add(new Move(x0, y0, 0, 0, 0)); // 原地不动 for (int[] d : dirs) { // 往 d 方向走 1,2,3,... 步 int x = x0 + d[0], y = y0 + d[1]; for (int step = 1; 0 < x && x <= SIZE && 0 < y && y <= SIZE; step++) { moves.add(new Move(x0, y0, d[0], d[1], step)); x += d[0]; y += d[1]; } } return moves.toArray(Move[]::new); } // 判断两个移动是否合法，即不存在同一时刻两个棋子重叠的情况 private boolean isValid(Move m1, Move m2) { int x1 = m1.x0, y1 = m1.y0; // 初始位置 int x2 = m2.x0, y2 = m2.y0; for (int i = 0; i < Math.max(m1.step, m2.step); i++) { // 每一秒走一步 if (i < m1.step) { x1 += m1.dx; y1 += m1.dy; } if (i < m2.step) { x2 += m2.dx; y2 += m2.dy; } if (x1 == x2 && y1 == y2) { // 重叠 return false; } } return true; } private int dfs(int i, int n, Move[][] allMoves, Move[] path) { if (i == n) { return 1; } int res = 0; outer: // 枚举当前棋子的所有合法移动 for (Move move1 : allMoves[i]) { // 判断合法移动 move1 是否有效 for (int j = 0; j < i; j++) { if (!isValid(move1, path[j])) { continue outer; // 无效，枚举下一个 move1 } } path[i] = move1; // 直接覆盖，无需恢复现场 res += dfs(i + 1, n, allMoves, path); // 枚举后续棋子的所有合法移动组合 } return res; } }
5.捕获黑皇后需要的最少移动次数
题目链接：3001. 捕获黑皇后需要的最少移动次数
现有一个下标从 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
两枚棋子不会同时出现在同一个格子上。
题解：
方法：分类
分类讨论：
如果车能直接攻击到皇后，答案是 1。
如果象能直接攻击到皇后，答案是 1。
其他情况，答案一定是 2：
- 如果车能攻击到皇后，但被象挡住，那么移走象，车就可以攻击到皇后，答案是 2。小知识：这在国际象棋中叫做「闪击」。
- 如果象能攻击到皇后，但被车挡住，那么移走车，象就可以攻击到皇后，答案是 2。
- 如果车不能攻击到皇后，那么车可以水平移动或者垂直移动，其中一种方式必定不会被象挡住，可以攻击到皇后，答案是 2。
判断能否直接攻击到：
- 对于车，如果和皇后在同一行或者同一列，且中间没有象，那么就可以直接攻击到皇后。
- 对于象，如果和皇后在同一斜线，且中间没有车，那么就可以直接攻击到皇后。
class Solution { public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) { if (a == e && (c != e || !inBetween(b, d, f)) || // 车直接攻击到皇后（同一行） b == f && (d != f || !inBetween(a, c, e)) || // 车直接攻击到皇后（同一列） c + d == e + f && (a + b != e + f || !inBetween(c, a, e)) || // 象直接攻击到皇后 c - d == e - f && (a - b != e - f || !inBetween(c, a, e))) { return 1; } return 2; } // m 在 l 和 r 之间（写不写等号都可以） private boolean inBetween(int l, int m, int r) { return Math.min(l, r) < m && m < Math.max(l, r); } }
另一种写法，如果 (m−l)⋅(m−r)>0，那么整数 m 不在整数 l 和 r 之间，
class Solution { public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) { if (a == e && (c != e || (d - b) * (d - f) > 0) || // 车直接攻击到皇后（同一行） b == f && (d != f || (c - a) * (c - e) > 0) || // 车直接攻击到皇后（同一列） c + d == e + f && (a + b != e + f || (a - c) * (a - e) > 0) || // 象直接攻击到皇后 c - d == e - f && (a - b != e - f || (a - c) * (a - e) > 0)) { return 1; } return 2; } }
6.可以被一步捕获的棋子数
题目链接：999. 可以被一步捕获的棋子数
给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 ‘R’ 表示。棋盘上还可能存在白色的象 ‘B’ 以及黑色的卒 ‘p’。空方块用字符 ‘.’ 表示。
车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。
注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。
返回白车 攻击 范围内 兵的数量。
示例 1：
输入：[[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“p”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“R”,“.”,“.”,“.”,“p”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“p”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”]]
输出：3
解释：
在本例中，车能够吃掉所有的卒。
示例 2：
输入：[[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“p”,“p”,“p”,“p”,“p”,“.”,“.”],[“.”,“p”,“p”,“B”,“p”,“p”,“.”,“.”],[“.”,“p”,“B”,“R”,“B”,“p”,“.”,“.”],[“.”,“p”,“p”,“B”,“p”,“p”,“.”,“.”],[“.”,“p”,“p”,“p”,“p”,“p”,“.”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”]]
输出：0
解释：
象阻止了车吃掉任何卒。
示例 3：
输入：[[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“p”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“p”,“.”,“.”,“.”,“.”],[“p”,“p”,“.”,“R”,“.”,“p”,“B”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“B”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“p”,“.”,“.”,“.”,“.”],[“.”,“.”,“.”,“.”,“.”,“.”,“.”,“.”]]
输出：3
解释：
车可以吃掉位置 b5，d6 和 f5 的卒。
提示：
board.length == 8
board[i].length == 8
board[i][j] 可以是 ‘R’，‘.’，‘B’ 或 ‘p’
只有一个格子上存在 board[i][j] == ‘R’
题解：
方法：数组
class Solution { private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public int numRookCaptures(char[][] board) { final int SIZE = 8; int x0 = 0; int y0 = 0; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { if (board[i][j] == 'R') { x0 = i; y0 = j; } } } int ans = 0; for (int[] d : DIRS) { int x = x0 + d[0]; int y = y0 + d[1]; while (0 <= x && x < SIZE && 0 <= y && y < SIZE && board[x][y] == '.') { x += d[0]; y += d[1]; } if (0 <= x && x < SIZE && 0 <= y && y < SIZE && board[x][y] == 'p') { ans++; } } return ans; } }
7.骑士在棋盘上的概率
题目链接：688. 骑士在棋盘上的概率
在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
骑士继续移动，直到它走了 k 步或离开了棋盘。
返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。
示例 1：
输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。
示例 2：
输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000
提示:
1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1
题解：
方法：动态规划
class Solution { public double knightProbability(int n, int k, int row, int column) { double[][][] f = new double[k + 1][n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { f[0][i][j] = 1; } } int[] dirs = {-2, -1, 2, 1, -2, 1, 2, -1, -2}; for (int h = 1; h <= k; ++h) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int p = 0; p < 8; ++p) { int x = i + dirs[p], y = j + dirs[p + 1]; if (x >= 0 && x < n && y >= 0 && y < n) { f[h][i][j] += f[h - 1][x][y] / 8; } } } } } return f[k][row][column]; } }
8.变为棋盘
题目链接：782. 变为棋盘
一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能交换任意两列或是两行的位置。
返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。
“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
示例 1:
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。
示例 2:
输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.
示例 3:
输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。
提示：
n == board.length
n == board[i].length
2 <= n <= 30
board[i][j] 将只包含 0或 1
题解：
方法：位运算 数学 状态压缩
class Solution { private int n; public int movesToChessboard(int[][] board) { n = board.length; int mask = (1 << n) - 1; int rowMask = 0, colMask = 0; for (int i = 0; i < n; ++i) { rowMask |= board[0][i] << i; colMask |= board[i][0] << i; } int revRowMask = mask ^ rowMask; int revColMask = mask ^ colMask; int sameRow = 0, sameCol = 0; for (int i = 0; i < n; ++i) { int curRowMask = 0, curColMask = 0; for (int j = 0; j < n; ++j) { curRowMask |= board[i][j] << j; curColMask |= board[j][i] << j; } if (curRowMask != rowMask && curRowMask != revRowMask) { return -1; } if (curColMask != colMask && curColMask != revColMask) { return -1; } sameRow += curRowMask == rowMask ? 1 : 0; sameCol += curColMask == colMask ? 1 : 0; } int t1 = f(rowMask, sameRow); int t2 = f(colMask, sameCol); return t1 == -1 || t2 == -1 ? -1 : t1 + t2; } private int f(int mask, int cnt) { int ones = Integer.bitCount(mask); if (n % 2 == 1) { if (Math.abs(n - ones * 2) != 1 || Math.abs(n - cnt * 2) != 1) { return -1; } if (ones == n / 2) { return n / 2 - Integer.bitCount(mask & 0xAAAAAAAA); } return (n / 2 + 1) - Integer.bitCount(mask & 0x55555555); } else { if (ones != n / 2 || cnt != n / 2) { return -1; } int cnt0 = n / 2 - Integer.bitCount(mask & 0xAAAAAAAA); int cnt1 = n / 2 - Integer.bitCount(mask & 0x55555555); return Math.min(cnt0, cnt1); } } }
