一? 糖果
我們看這個藍橋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，高度 hfor (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); // 開始 DFSbreak; // 找到起點后退出循環}}}printf("%d", res); // 輸出結果return 0; }首先這個具有方向性質的首先就是考慮用向量數組，這樣就可以幫助我們去移動，然后這個也有三個條件
1? 不可以越界
2? 遇到#要進行不走
3? 走過的路不走
所以把握了這個很簡單就可以寫出來了
?
總結
首先我們現在越來越熟練這個dfs了，然后還熟悉記憶化搜索和剪枝的操作
這些都是十分重要對于搜索類型的題目，所以我們就要好好掌握
這里蘊含了兩個條件
首先就是方向的移動
其次就是有沒有拿過和有沒有走過這些狀態，這些狀態是要用數組記錄下來去使用的我們可以使用循環，也可以使用很多的方法，所以if和for這里面很重要
遞歸，for，if組成就構成了搜索
