棋盘上有效移动组合的数目
难度:
标签:
题目描述
有一个 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.lengthn == positions.length1 <= n <= 4pieces只包含字符串"rook"，"queen"和"bishop"。- 棋盘上总共最多只有一个后。
1 <= xi, yi <= 8- 每一个
positions[i]互不相同。
代码结果
运行时间: 300 ms, 内存: 16.9 MB
/*
* 思路：
* 1. 使用Java Stream API实现递归搜索的逻辑。
* 2. 将每种可能的移动路径放入Stream中进行处理。
* 3. 过滤掉无效的移动组合，计算有效的组合数量。
*/
import java.util.stream.*;
public class ChessMovesStream {
private static final int[][] ROOK_DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static final int[][] QUEEN_DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
private static final int[][] BISHOP_DIRECTIONS = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
public int countValidMoves(String[] pieces, int[][] positions) {
return countValidMoves(pieces, positions, 0, new boolean[8][8]);
}
private int countValidMoves(String[] pieces, int[][] positions, int index, boolean[][] occupied) {
if (index == pieces.length) return 1;
String piece = pieces[index];
int r = positions[index][0] - 1;
int c = positions[index][1] - 1;
int[][] directions = getDirections(piece);
return Arrays.stream(directions)
.flatMapToInt(dir -> IntStream.range(1, 8)
.map(step -> new int[]{r + dir[0] * step, c + dir[1] * step})
.filter(pos -> isValid(pos, occupied))
.map(pos -> {
occupied[pos[0]][pos[1]] = true;
int result = countValidMoves(pieces, positions, index + 1, occupied);
occupied[pos[0]][pos[1]] = false;
return result;
})
).sum();
}
private boolean isValid(int[] pos, boolean[][] occupied) {
int r = pos[0], c = pos[1];
return r >= 0 && r < 8 && c >= 0 && c < 8 && !occupied[r][c];
}
private int[][] getDirections(String piece) {
switch (piece) {
case "rook": return ROOK_DIRECTIONS;
case "queen": return QUEEN_DIRECTIONS;
case "bishop": return BISHOP_DIRECTIONS;
default: throw new IllegalArgumentException("Invalid piece type");
}
}
}解释
方法:
这个解决方案使用了深度优先搜索 (DFS) 来遍历所有可能的棋子移动组合，并验证每个组合的有效性。每种棋子（车、后、象）可以沿不同的方向移动到棋盘的不同位置。对每个棋子，算法首先计算出所有可能的单次移动路径。然后，使用DFS尝试所有可能的移动组合，同时利用一个验证函数来确保没有两个棋子在同一时间占据同一个位置或者互换位置。验证函数比较两个路径的每个步骤，检查是否存在冲突。最终，算法返回所有有效组合的数量。
时间复杂度:
O(M^n * n^2)
空间复杂度:
O(n * M)
代码细节讲解
🦆
在定义函数`f(x: int, y: int) -> int`时，选择将坐标转换为唯一数值的原因是什么？这种转换对算法的性能有何影响？
▷🦆
为什么在存储棋子的移动路径时，需要记录从起始点到每个可能的终点的完整路径而不是仅存储终点位置？
▷🦆
在递归函数`dfs`中，如何处理棋子之间的位置冲突？具体的验证函数`validate`如何确保没有两个棋子占据同一位置或互换位置？
▷🦆
算法中是否考虑了棋子的移动可能导致棋子重叠的情况，如果考虑了，是如何处理的？
▷