目录
写在前面：
题目：1114. 棋盘问题 - AcWing题库
题目描述：
输入格式：
输出格式：
数据范围：
输入样例：
输出样例：
解题思路：
代码：
AC ！！！！！！！！！！
写在最后：
写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：1114. 棋盘问题 - AcWing题库
题目描述：
输入格式：
输入含有多组测试数据。
每组数据的第一行是两个正整数 n, k，用一个空格隔开，
表示了将在一个 n ∗ n 的矩阵内描述棋盘，以及摆放棋子的数目。
当为-1 -1时表示输入结束。
随后的 n 行描述了棋盘的形状：每行有 n 个字符，其中 # 表示棋盘区域，
. 表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出格式：
对于每一组数据，给出一行输出，输出摆放的方案数目 C （数据保证 C < 231）。
数据范围：
n ≤ 8,k ≤ n
输入样例：
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1输出样例：
2
1解题思路：
我们使用深度优先搜索的时候，
第一个要注意的点是搜索的顺序，
因为我们要保证，
我们写出的递归结构能够遍历所有情况。
（以上递归搜索的基本思路，多熟悉总是好的）
接下来是具体思路：
根据题意我们可以总结出两个问题：
1. 我们只能在‘#’位置下棋，不能在‘.’位置下棋；
2. 每行每列只允许下一个棋，那如何遍历棋盘的所有情况？
第一个问题我们加判断即可，
第二个问题，我们需要模拟一下：（以棋盘是3行3列为例）
画一个递归搜索树：
我们假设每一个横线是一行，每次递归搜索下一列：
根节点：
然后，第一行能放的位置有，1、2、3列，
我们据此往下递归搜索：
放过的列在继续递归之后就不能放了：
继续递归搜索：
我们发现这其实就是一个全排列，我们根据全排列的思想去做即可。
下面是代码实现：
代码：
//包常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
const int N = 10;
//计数
int res;
char g[N][N];
//记录这一列有没有下棋
bool used[N];
void dfs(int u, int cnt)
{
//下的棋数符合题目要求，方案++
if(cnt == k)
{
res++;
return;
}
//已经到行底了
if(u == n) return;
for(int i = 0; i < n; i++)
{
if(!used[i] && g[u][i] == '#')
{
used[i] = true;
dfs(u + 1, cnt + 1);
used[i] = false;//恢复现场
}
}
//如果前面（下的棋数符合题目要求，方案++），就会返回，导致到不了下一行，这里让他强行往下走一行
dfs(u + 1, cnt);
}
int main()
{
//多组输入
while(cin >> n >> k && n > 0 && k > 0)
{
for(int i = 0; i < n; i++)
{
cin >> g[i];
}
//每组输入重新计数
res = 0;
dfs(0, 0);
printf("%d\n", res);
}
return 0;
}AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。文章来源：https://www.toymoban.com/news/detail-407145.html
之后我还会输出更多高质量内容，欢迎收看。文章来源地址https://www.toymoban.com/news/detail-407145.html
到了这里，关于【AcWing刷题】蓝桥杯专题突破-深度优先搜索-dfs（8）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
