不得不说,接触DFS和BFS将近几个月了(当然不是一直在练,hh),就会走个迷宫,hh.
今天学到了一些新的东西,分享一下.
目前我接触到的大致有两类:
1、地图类:
a、迷宫(各种迷宫)
b、最短路(迷宫的最少次数)
2、状态分解
不同的分支(选 or 不选,当然也有可能有多个状态(分支))(重要的是我们遇到题目时能够转化成我们学到的知识)
说到DFS(网上有很多介绍就不说了),我们首先想到的就是递归.
可以将递归想象成我们去递归一棵树,树中的每个节点对应的状态个数都是相同的(也就是子问题再分解成子问题)
下面通过几道题来细细品味一下:
1、链接: 题目链接: (递归实现指数型枚举)
题目大致描述:从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案.
代码部分：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
int a[10];
int n,m;
vector<int>ve;
int main(void) {
void DFS(int pos);
scanf("%d%d",&n,&m);
DFS(1);
return 0;
}
void DFS(int pos) {
if(pos == n + 1) {
for(int i = 0; i < ve.size(); i ++) {
cout<<ve[i]<<" ";
}
cout<<endl;
return ;
}
// 选这个数与不选都要 pos + 1,为了保证最后的结束条件,只需要把选的数存到vector中即可
ve.push_back(pos); // 两种选择的顺序不同得到的结果也大不相同
DFS(pos + 1); // 选这个数
ve.pop_back();
/*
回溯:（还原现场）如果子问题求解失败,程序需要重新回到当前问题去寻找其他的变换
路线,因此把当前问题缩小为子问题时所做的对当前问题状态所产生影响的事情应
该全部失效.
*/
DFS(pos + 1); // 不选这个数
return ;
}
2、 题目链接
题目描述:从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
代码部分:
/*
只要在上述代码中加入
if(ve.size() > m || ve.size() + (n - pos + 1) < m) return ;
进行剪枝,当发现运行到的答案根本不可能是,直接结束当前状态。
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
int a[10];
int n,m;
vector<int>ve;
int main(void) {
void DFS(int pos);
scanf("%d%d",&n,&m);
DFS(1);
return 0;
}
void DFS(int pos) {
if(ve.size() > m || ve.size() + (n - pos + 1) < m) return ;
if(pos == n + 1) {
for(int i = 0; i < ve.size(); i ++) {
cout<<ve[i]<<" ";
}
cout<<endl;
return ;
}
ve.push_back(pos); // 两种选择的顺序不同得到的结果也大不相同
DFS(pos + 1);
ve.pop_back();
DFS(pos + 1);
return ;
}
3、 题目链接
题目描述 : 把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
这道题与之前两道题的差别就在于 需要 标记每个数,避免重复.
另外这道题还可以用 全排列函数:next_permutation(),进行提交,不过这个函数还
是有必要练习一下的,为之后的搜索打下基础,不然就得像菜菜的我一样重新学习,感
觉到深深的负罪感.hhhhhhhhhhh
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 20;
int num[maxn];
bool vis[maxn];
int n;
int main(void) {
void DFS(int pos);
scanf("%d",&n);
DFS(1);
return 0;
}
void DFS(int pos) {
if(pos == n + 1) {
for(int i = 1; i <= n; i ++) {
printf("%d ",num[i]);
}
cout<<endl;
return ;
}
for(int i = 1; i <= n; i ++) {
if(!vis[i]) {
vis[i] = 1;
num[pos] = i; // 符合条件的数保存到数组中
DFS(pos + 1);
vis[i] = 0; // 还原现场(这里不理解可以重点看上面关于这个名词的解释)
}
}
return ;
}
几道搜索题(关于状态) :
PS:这类问题都是先假设最大需要多少个才能满足条件,然后通过DFS进行比较找到最少的
(猛一看与背包问题有点像,实际上不是,当然万能的DP对于处理这种问题轻而易举,无奈
菜菜的自己想不出来呀,就这个都感觉很吃力,加油!)
1、 题目链接 https://www.acwing.com/problem/content/167/
题目描述：小猫爬山(可以在AcWing题库搜索)
代码部分:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 20;
int cat[maxn],cab[maxn],n,w,ans,sum; // cat：猫的重量,cab: 每个缆车的容量
int main(void) {
void solve();
scanf("%d%d",&n,&w);
for(int i = 1; i <= n; i ++) {
scanf("%d",&cat[i]);
}
ans = n;
solve();
cout<<ans<<endl;
return 0;
}
void DFS(int pos,int num) { // num : 缆车的数量
if(num >= ans) return ; // 剪枝
if(pos == n + 1) {
ans = min(ans,num); // 这里也可以不用比较,因为上面较大时就直接返回到上一个状态了
return ;
}
for(int i = 1; i <= num; i ++) { // 看在已有的缆车中是否可以容纳新的猫
if(cat[pos] + cab[i] <= w) {
cab[i] += cat[pos];
DFS(pos + 1,num);
cab[i] -= cat[pos]; // 还原现场,看是否有其他的更好的解决方法
}
}
cab[num + 1] = cat[pos]; // 无法容纳时再开一个缆车(此时缆车内的重量就是前一个容纳不下的)
DFS(pos + 1,num + 1); // 缆车数量 + 1
cab[num + 1] = 0; // 还原现场
return ;
}
bool cmp(int a,int b) {
return a > b;
}
void solve() {
sort(cat + 1,cat + 1 + n,cmp); // 从大到小考虑(因为容量更大的与其他缆车的可容量匹配更少)
// 这里也可以写一个reverse(cat + 1,cat + 1 + n)函数就不用排序了
DFS(1,0);
return ;
}
2、 题目链接
分考场:蓝桥杯系统里面的一道题(与上一道题十分类似)
代码部分:
/*
与图的着色问题类似,但不完全是。
*/
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 105;
int grach[maxn][maxn]; // 建立图(两个人之间相互认识,所以需要建立无向图)
int cnt[maxn][maxn],ans[maxn]; // cnt 数组表示第几个教室有都是谁 cnt[1][2] = 3,表示第一个教室的第二个位置的 id 是 3, ans 数组表示 每个教室的人数。
int n,m,L,R,res = INF; // 假设刚开始需要无穷多个教室。
int main(void) {
void input();
void solve();
while(scanf("%d%d",&n,&m) != EOF) {
input();
solve();
}
return 0;
}
void input() {
memset(ans,0,sizeof(ans));
memset(grach,0,sizeof(grach));
memset(cnt,0,sizeof(cnt));
for(int i = 1; i <= m; i ++) {
scanf("%d%d",&L,&R);
grach[L][R] = 1;
grach[R][L] = 1;
}
res = INF;
return ;
}
/* 每次需要对当前这个人进行判断,看当前这个人与已有的教室里面的人数是否有认识的,
如果没有认识的就放在当前教室,当然不一定只能放在一个教室，也有可能好几个教室
都有当前这个人不认识的，所以就需要回溯。
如果说所有教室都有当前人认识的人，那么就需要另外开辟一个教室。
*/
void DFS(int id,int count) { // count : 教室的数量
if(count >= res) return ; // 剪枝,我之前已经得到一个教室的数量，如果说现在所需要的教室数量超过之前的数量,说明一定不是最优结果，也没有必要继续往下走了
if(id > n) {
res = min(count,res); // 判断完所有人后得到需要考场的数目,与之前的进行比较得到一个最小值。
return ;
}
for(int i = 0; i < count; i ++) { // 遍历每个教室
int len = ans[i],c = 0;
for(int j = 0; j < len; j ++ ) { // 遍历当前教室里的每个人
if(grach[id][cnt[i][j]] == 0 || grach[cnt[i][j]][id] == 0) {
c ++;
}
}
if(c == len) {
cnt[i][ans[i] ++] = id;
DFS(id + 1,count); // 这里 count 为什么不用改变？(可以把这个学生放在当前的教室,所以不用改变)
ans[i] --; // 回溯,看其他教室是否有满足的情况
}
}
cnt[count][ans[count] ++] = id;
DFS(id + 1,count + 1);
ans[count] --; // 回溯(同上)
}
void solve() {
DFS(1,0);
printf("%d\n",res);
return ;
}
后续更新ing....
tql