算法day4 dfs搜索2题
一 糖果
我们看这个蓝桥A组真题
首先我们看这个题目说有M种的糖果，K颗一包，N包糖果
第一行就是输入M，K，N的数量
后面就是输入每个糖果在每包里面的种类
然后问我们最少要用几包糖果才可以把所有种类的糖果都吃一遍
如果不可以吃完所有种类的糖果，就直接返回-1
当我在竞赛场上一定要冷静，思考这个题目是属于什么类型的
很显然，这个糖果有一个选和不选，那么就可以快速想到这个dfs来解决，如果不行的话就优化代码，可以去看这篇文章里面很详细的讲述优化算法 状态dp-CSDN博客
然后我们先来想一下这个怎么写
首先这里有很多的糖果，每个糖果只有选择和不选择，就像二叉树一样，那么递归也就只有两层，一个用于左子树，一个用于右子树，这两个递归分别代表选择和不选择
然后我们就再进行分析，搞定了递归的话，那么我后面就要搞定条件了
题目给的限制条件是要吃完所有的糖果类型，那么我们可以用一个状态数组来实现这个种类的糖果到底吃没吃，这样就可以知道到底有没有吃完所有的糖果了
我们来实现一下
代码都是作者自己敲出来的，如果有更好的代码，欢迎大家指出#include<bits/stdc++.h> #include<cstring> #include<unordered_map> using namespace std; const int N = 110; int n,m,k; //包数，种类，几个一包 int candy[N][N]; bool st[N]; //标记对饮糖果的种类 int mincount=1e6; bool judge(){ for(int i=1;i<=m;i++){ if(!st[i])return false; } return true; } //x表示当前包 void dfs(int x,int count){ //减枝 if(count>mincount) return ; if(x>n){ if(judge()){ mincount=min(mincount,count); } return ; } // 选择当前包 bool temp[N]; // 临时保存 st 的状态 memcpy(temp, st, sizeof(st)); // 保存当前状态 for (int i = 1; i <= k; i++) { st[candy[x][i]] = true; } dfs(x + 1, count + 1); // 恢复 st 的状态 memcpy(st, temp, sizeof(temp)); //不选择 dfs(x+1,count); } int main(){ scanf("%d %d %d",&n,&m,&k); memset(candy,0,sizeof(candy)); for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ scanf("%d",&candy[i][j]); } } dfs(1,0); if(mincount==1e6){ printf("-1\n"); return 0; } printf("%d\n",mincount); return 0; }首先这个输入就没有必要说了，来说说这个dfs，首先这个dfs我一开始是犯了一个很严重的错误的，就是这个糖果的状态判断
//选择 //增添对这个糖果的标记 for(int i=1;i<=k;i++){ st[candy[x][i]]=true; } dfs(x+1,count+1); //取消对这个口味的标记 for(int i=1;i<=k;i++){ st[candy[x][i]]=false; } //不选择 dfs(x+1,count);这个是我之前的写的代码
我当时是想着如果回溯就恢复原来的状态，但是我们忽略了还有之前已经找过的糖果状态是true，我这里设置全是true，所以会导致结果不对，后来才想到这个是需要上一次的状态的，所以这里就直接用了一个临时的数组来存储临时的状态，当回溯的时候就直接返回这个状态就好了，这个题目主要是难在这个状态我们该怎么去设置，dfs不难
二 入门
我们来看这种带有迷宫性质的，我们不适用广度优先搜索，使用dfs该怎么解决
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 30; int w, h; // 宽度和高度 int res; // 结果 char map[N][N]; // 地图 bool st[N][N]; // 状态 int ax[] = {-1, 0, 1, 0}; int ay[] = {0, 1, 0, -1}; void dfs(int x, int y) { for (int i = 0; i < 4; i++) { int a = x + ax[i]; int b = y + ay[i]; // 边界条件 if (a >= h || a < 0 || b >= w || b < 0) continue; if (map[a][b] == '#') continue; if (st[a][b]) continue; st[a][b] = true; res++; dfs(a, b); } } int main() { scanf("%d %d", &w, &h); // 注意顺序：宽度 w，高度 h for (int i = 0; i < h; i++) { scanf("%s", map[i]); // 按行读取地图 } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (map[i][j] == '@') { st[i][j] = true; // 标记起点为已访问 res = 1; // 初始化结果，包括起点 dfs(i, j); // 开始 DFS break; // 找到起点后退出循环 } } } printf("%d", res); // 输出结果 return 0; }首先这个具有方向性质的首先就是考虑用向量数组，这样就可以帮助我们去移动，然后这个也有三个条件
1 不可以越界
2 遇到#要进行不走
3 走过的路不走
所以把握了这个很简单就可以写出来了
总结
首先我们现在越来越熟练这个dfs了，然后还熟悉记忆化搜索和剪枝的操作
这些都是十分重要对于搜索类型的题目，所以我们就要好好掌握
这里蕴含了两个条件
首先就是方向的移动
其次就是有没有拿过和有没有走过这些状态，这些状态是要用数组记录下来去使用的我们可以使用循环，也可以使用很多的方法，所以if和for这里面很重要
递归，for，if组成就构成了搜索