一、题目2056. 棋盘上有效移动组合的数目
有一个 8 ∗ 8 8 * 8 8∗8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 p i e c e s [ i ] pieces[i] pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组positions ，其中 p o s i t i o n s [ i ] = [ r i , c i ] positions[i] = [r_i, c_i] positions[i]=[ri,ci] 表示第 i 个棋子现在在棋盘上的位置为 ( r i , c i ) r_i, c_i) ri,ci) ，棋盘下标从 1 开始。
棋盘上每个棋子都可以移动 至多一次 。每个棋子的移动中，首先选择移动的 方向 ，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：
-
1.车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1) 或者 (r, c-1) 移动。
-
2.后可以 水平竖直或者斜对角 从 (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) 移动。
-
3.象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
-
4.移动组合 包含所有棋子的 移动 。每一秒，每个棋子都沿着它们选择的方向往前移动 一步 ，直到它们到达目标位置。所有棋子从时刻 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 种移动组合。
但是，有两个是不有效的移动组合：
1、 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。
2、将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。
三、数据范围
- n == pieces.length
- n == positions.length
- 1 <= n <= 4
- pieces 只包含字符串 “rook” ，“queen” 和 “bishop” 。
- 棋盘上最多只有一个后。
- 1 <= r i r_i ri, c i c_i ci <= 8
- 每一个 p o s i t i o n s [ i ] positions[i] positions[i] 互不相同。
四、思路
首先数据范围很小，可以无脑进行dfs/bfs搜索出所有的可能，这里使用bfs常数大一点，但是比较好写一点。
每次取出一个棋子，放入所有移动的可能（包括不移动），放完所有的棋子检查当前棋盘和合法性即可。
五、代码
class Solution {
public:
int n;
int dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
{1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int vis[10][10];
int countCombinations(vector<string>& pieces,
vector<vector<int>>& positions) {
n = pieces.size();
vector<pair<int, int>> moves;
return bfs(pieces, positions, moves);
}
int bfs(vector<string>& pieces, vector<vector<int>>& positions,
vector<pair<int, int>>& moves) {
// 队列用于BFS，保存每一层的状态
queue<pair<vector<pair<int, int>>, int>> q; // 状态，当前棋子索引
q.push({moves, 0});
int totalCombinations = 0;
while (!q.empty()) {
auto [currentMoves, p] = q.front();
q.pop();
if (p == n) {
if (valid(positions, currentMoves)) {
totalCombinations++;
}
continue;
}
int start = (pieces[p] == "bishop" ? 1 : 0);
int add = (pieces[p] == "queen" ? 1 : 2);
int x = positions[p][0], y = positions[p][1];
// 保持当前棋子不动
currentMoves.push_back({0, 0});
q.push({currentMoves, p + 1});
currentMoves.pop_back();
// 遍历所有可能的移动方向
for (int d = start; d < 8; d += add) {
int step = 1;
int nx = x + dir[d][0], ny = y + dir[d][1];
while (nx >= 1 && nx <= 8 && ny >= 1 && ny <= 8) {
currentMoves.push_back({d, step});
q.push({currentMoves, p + 1});
currentMoves.pop_back();
nx += dir[d][0];
ny += dir[d][1];
step++;
}
}
}
return totalCombinations;
}
bool valid(vector<vector<int>>& positions, vector<pair<int, int>>& moves) {
memset(vis, 0, sizeof(vis));
int done = 0;
for (auto& [d, step] : moves) {
done += (step == 0);
}
for (int r = 1; done < n; r++) {
for (int i = 0; i < n; i++) {
auto& [d, step] = moves[i];
int x = positions[i][0] + min(step, r) * dir[d][0];
int y = positions[i][1] + min(step, r) * dir[d][1];
if (vis[x][y] == r)
return false;
vis[x][y] = r;
if (step == r)
done++;
}
}
return true;
}
};