1114棋盘问题acwing（深度优先搜索）

题目描述

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 kk 个棋子的所有可行的摆放方案数目 CC。

输入格式

输入含有多组测试数据。

每组数据的第一行是两个正整数 n,kn,k，用一个空格隔开，表示了将在一个 n∗nn∗n 的矩阵内描述棋盘，以及摆放棋子的数目。当为-1 -1时表示输入结束。

随后的 nn 行描述了棋盘的形状：每行有 nn 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目 CC （数据保证 C<231C<231）。

数据范围

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为棋盘大小n，number为需要放置的棋子数k vector<bool> v; // 标记列是否被占用，v[i]为true表示第i列已被使用 vector<vector<char>> 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); // 递归处理下一行，棋子数+1 v[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, vector<char>(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(x+1, count+1); 进入下一行。递归返回后，取消该列的占用状态（v[i] = false;），以便尝试其他方案。 终止条件 棋子数量等于 k：找到一种有效方案，res++ 并返回。超出行界限 x > n：无效路径，直接返回。

---

时间复杂度分析

最坏情况下，n=8，k=8，即 8! ≈ 40,320，这种规模可以接受。