上一个专题是动态规划,然而因为动态规划种类繁多,只能蜻蜓点水每个知识点写一个入门题。如果每个知识点写得比较深入会极为耗时,因此公众号的专题还是只能作为入门用途,尽可能多的写不同的知识点。
然而即使是对动态规划做比较简单的归纳总结,一路下来却也感觉自己进步很多,比如说在做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 -1
Sample 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算法日常。