搜索专题1 | 棋子摆放 POJ - 1321
上一个专题是动态规划，然而因为动态规划种类繁多，只能蜻蜓点水每个知识点写一个入门题。如果每个知识点写得比较深入会极为耗时，因此公众号的专题还是只能作为入门用途，尽可能多的写不同的知识点。
然而即使是对动态规划做比较简单的归纳总结，一路下来却也感觉自己进步很多，比如说在做DP专题之前我对于多维的动态规划是比较忌惮的，因为见的不多，说白了就是题目做得太少，陌生感太强。写到后面就觉得多维的DP也很普通，更重要的是动态规划思维的转变。
在结束DP专题后，这一次我们来做一个搜索专题，搜索算法主要是DFS和BFS，以及一些优化技巧。虽然动态规划和搜索算法存在比较大的差异，但是在完成动态规划专题后再来看搜索算法就会觉得很简单，并不是说搜索算法简单，而是理解起来会容易很多。
这就像打游戏，高难度的情况下能打通关，那么低难度的就会是小菜一碟。
本次搜索专题大概还是做十来道题目，每个题目都会有一些知识点，一起开始学习吧！
题目描述：
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1Sample Output
2 1本题知识点：
1 DFS算法入门
DFS算法也就是深度优先搜索算法，表示遍历空间时一直往深处搜索（远离根部），DFS通常有一个起点，可以看作是树根，搜索过程中优先往叶子方向搜索，到达叶子节点后进行回溯。
2 回溯，还原现场
在搜索的过程中，如果DFS带有状态，则在DFS函数执行完成之后，需要做一个还原现场的操作，保证在for循环中不影响全局状态，也可以不设置全局状态，但是通常情况下使用全局状态能够节省很多内存开销。
本题中是搜索棋盘可以放置的棋子，棋子不能够在同一行或者同一列，然后还可能有障碍物不能放置棋子。示意图大概如下：
从位置0-0开始，每次DFS到下一行，每次回溯的时候会还原当前记录的数量值cnt。
注意对于每一行来说可以不用放置棋子。
源代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string s[10];
int line[10]; //记录第i个棋子放在第几列
int ans = 0;
int n, k;
int cnt = 0;
void dfs(int row) {
if (cnt == k) {
// 刚好达到k个
ans++;
return;
}
if (row >= n) {
// 超出限制
return;
}
// col代表列数
for (int col = 0; col < n; col++) {
// 只有#能够放置棋子
if (s[row][col] == '#')
{
int ok = 1;
// line[j]当前记录每一行棋子所在列
for (int j = 0; j < cnt; j++)
{
// 如果棋子刚好在这一列，则不能放置
if (line[j] == col) {
ok = 0;
break;
}
}
if (ok) {
// 如果可以放置，则放置，line记录每次放置棋子所在的列
line[cnt++] = col;
dfs(row + 1);
// 完成后重置状态
cnt--;
}
}
}
// 不放棋子的情况
dfs(row + 1);
}
int main() {
while (cin >> n >> k) {
memset(line, -1, sizeof(line));
ans = 0, cnt = 0;
if (n == -1 && k == -1)
break;
// n行地图
for (int i = 0; i < n; i++)
cin >> s[i];
// 从第0行开始搜索
dfs(0);
cout << ans << endl;
}
return 0;
}温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。