写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：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 #include #include #include 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 ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
