行业协会网站模板,随申办app下载,怎么做网站聊天视频直播,制作主页的软件题目描述
在一个给定形状的棋盘#xff08;形状可能是不规则的#xff09;上面摆放棋子#xff0c;棋子没有区别。
要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列#xff0c;请编程求解对于给定形状和大小的棋盘#xff0c;摆放 kk 个棋子的所有可行的摆放…题目描述
在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。
要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放 kk 个棋子的所有可行的摆放方案数目 CC。
输入格式
输入含有多组测试数据。
每组数据的第一行是两个正整数 n,kn,k用一个空格隔开表示了将在一个 n∗nn∗n 的矩阵内描述棋盘以及摆放棋子的数目。当为-1 -1时表示输入结束。
随后的 nn 行描述了棋盘的形状每行有 nn 个字符其中 # 表示棋盘区域 . 表示空白区域数据保证不出现多余的空白行或者空白列。
输出格式
对于每一组数据给出一行输出输出摆放的方案数目 CC 数据保证 C231C231。
数据范围
n≤8,k≤nn≤8,k≤n
输入样例
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1输出样例 2
1代码如下
#include bits/stdc.h
using namespace std;// 全局变量声明
int res 0; // 结果存储可行方案数目
int nn 0, number 0; // nn为棋盘大小nnumber为需要放置的棋子数k
vectorbool v; // 标记列是否被占用v[i]为true表示第i列已被使用
vectorvectorchar b; // 棋盘存储#和.b[x][i]表示第x行第i列// 深度优先搜索函数
// 参数x当前处理的行号count已放置的棋子数目
void dfs(int x, int count) {// 如果已放置number个棋子方案数1并返回if (count number) {res;return;}// 若超出棋盘行数直接返回if (x nn) {return;}// 遍历当前行的所有列尝试放置棋子for (int i 1; i nn; i) {// 如果当前列未被占用且该位置可放置if (!v[i] b[x][i] #) {v[i] true; // 标记该列为已使用dfs(x 1, count 1); // 递归处理下一行棋子数1v[i] false; // 回溯撤销列的标记}}// 不放置当前行的棋子直接处理下一行dfs(x 1, count);
}int main() {// 循环处理多组输入直到输入-1 -1为止while (1) {cin nn number;if (nn -1 number -1)break;// 初始化棋盘和标记数组b.assign(nn 1, vectorchar(nn 1, 0));v.assign(nn 1, false);// 读取棋盘数据注意行和列从1开始存储for (int i 1; i nn; i) {for (int j 1; j nn; j) {cin b[i][j];}}res 0; // 重置结果dfs(1, 0); // 从第1行开始搜索初始已放置0个棋子cout res endl; // 输出当前棋盘的方案数}return 0;
}/*
思路详解
1. **问题分析**在n×n棋盘的#位置放置k个棋子要求任意两个棋子不同行不同列。需要计算所有可行方案数。
2. **搜索策略**采用深度优先搜索DFS逐行处理每行有两种选择放置或不放置棋子。
3. **放置规则**- 在当前行选择一个未被占用的列对应#位置。- 标记该列递归处理下一行。- 回溯时撤销列的标记以尝试其他可能的列。
4. **剪枝与终止条件**- 当已放置k个棋子时方案数1。- 当处理完所有行时终止当前路径。
5. **复杂度优化**逐行处理避免行冲突列标记数组避免列冲突确保每行每列最多一个棋子。
6. **递归过程**每次递归处理下一行确保行号递增从而覆盖所有行选择组合。
*/代码说明
DFS 递归搜索 遍历当前行 x 的所有列如果当前格子是 # 且该列未被占用就放置棋子并递归搜索下一行。不放置棋子直接跳到下一行保证搜索完整棋盘。 回溯 递归调用 dfs(x1, count1); 进入下一行。递归返回后取消该列的占用状态v[i] false;以便尝试其他方案。 终止条件 棋子数量等于 k找到一种有效方案res 并返回。超出行界限 x n无效路径直接返回。 时间复杂度分析
最坏情况下n8k8即 8! ≈ 40,320这种规模可以接受。
