DFS入门级模板看CSDN文章 DFS入门级（模板）_dfs模型-CSDN博客
题目一 烤鸡
题目描述 猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 1010 种配料的所有搭配方案。
输入格式 一个正整数 n ，表示美味程度。
输出格式 第一行，方案总数。
第二行至结束，1010 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 0。
输入输出样例 输入 #1
输出 #1
1 2 3 4 5 6 7 8 9 10 11 10 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 20; int n; // 美味程度 int arr[N]; // 存储当前方案 int res = 0; // 存储方案数 int mem[59955][N]; // 存储方案 // x表示当前枚举到了哪一位，sum表示当前已经选了的调料的总质量 void dfs(int x, int sum) { if (sum > n) return; // 剪枝 if (x > 10) { if (sum == n) { res++; for (int i = 1; i <= 10; i++) { mem[res][i] = arr[i]; // 存储方案到mem数组 } } return; // 返回遗漏的 return 语句 } for (int i = 1; i <= 3; i++) { arr[x] = i; dfs(x + 1, sum + arr[x]); // 更新sum的值 arr[x] = 0; // 恢复现场(回溯)，这行可以省略，因为后面的数据会将原有的数据直接覆盖掉 } } int main() { scanf("%d", &n); dfs(1, 0); // 从第1个位置开始，当前的sum为0 printf("%d\n", res); for (int i = 1; i <= res; i++) { for (int j = 1; j <= 10; j++) { printf("%d ", mem[i][j]); } printf("\n"); } return 0; }
题目二 火柴棒等式
题目描述 给你 n 根火柴棍，你可以拼出多少个形如A +B =C 的等式？等式中的 A、 B、 C*是用火柴棍拼出的整数（若该数非零，则最高位不能是 00）。用火柴棍拼数字 0∼90∼9 的拼法如图所示：
注意：
加号与等号各自需要两根火柴棍；
如果 ≠A\=B ，则 A +B =C 与 B*+A =*C 视为不同的等式
n 根火柴棍必须全部用上。
输入格式 一个整数 n(1≤n≤24)n (1≤n ≤24)。
输出格式 一个整数，能拼成的不同等式的数目。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=10000; int n; int arr[N];//数值 int nums[N]={6,2,5,5,4,5,6,3,7,6};//火柴数(各个数值对应的火柴数) int res=0; //计算火柴数量(x这个数字对应的火柴数量,x这个数字可能大于9) int col(int x) { if(nums[x]) return nums[x];//x属于0到9时 else{ int sumFire=0; while(x){ sumFire+=nums[x%10]; x/=10; } return sumFire; } } //x表示第x的位置,y表示当前所用的火柴总数 void dfs(int x,int sum){ if(sum>n) return ;//剪枝 if(x>3){ if(arr[1]+arr[2]==arr[3]&&sum==n){//分别满足两个条件（一是数值相加相等，而是火柴数量相等） res++; } return; } for(int i=0;i<=1000;i++){ arr[x]=i; dfs(x+1,sum+col(i));//递归下一个位置 arr[x]=0;//恢复现场 } } int main(){ scanf("%d",&n); n-=4;//加号和等于分别要用到2根火柴 dfs(1,0); printf("%d",res); return 0; }
题目三 PERKET
题目描述 Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s 和苦度 b*。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
输入格式 第一行一个整数 n*，表示可供选用的食材种类数。
接下来 n* 行，每行 22 个整数 si和 b i，表示第 i 种食材的酸度和苦度。
输出格式 一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
输入输出样例 输入 #1 复制
输出 #1
输入 #2
输出 #2
输入 #3
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=20; int n; int acid[N],bitter[N]; int res =1e9;//存答案 int st[N]; //0表示没考虑到，1表示选，2表示不选 void dfs(int x){ if(x>n){ bool has_t1=false;//是否有调料(题目要求至少有一种调料) int sum1=1;//存酸度之积 int sum2=0;//存苦度之和 for(int i=1;i<=n;i++){ if(st[i]==1){ has_t1=true; sum1*=acid[i]; sum2+=bitter[i]; } } if(has_t1) res=min(res,abs(sum1-sum2)); return; } //选 st[x]=1; dfs(x+1); st[x]=0; //恢复现场 //不选 st[x]=2; dfs(x+1); st[x]=0;//恢复现场 } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d %d",&acid[i],&bitter[i]); } dfs(1); printf("%d",res); return 0; }
题目四 迷宫类进阶
题目描述
不是任何人都可以进入桃花岛的，黄药师最讨厌像郭靖一样呆头呆脑的人。所以，他在桃花岛的唯一入口处修了一条小路，这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩，我们认为是安全的，而有的瓷砖一踩上去就会有喷出要命的毒气，那你就死翘翘了，我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上，但它也必须是安全的才行。
由于你是黄蓉的朋友，她事先告诉你哪些砖是安全的、哪些砖是不安全的，并且她会指引你飞到第一块砖上（第一块砖可能在任意安全位置），现在她告诉你进入桃花岛的秘密就是：如果你能走过最多的瓷砖并且没有死，那么桃花岛的大门就会自动打开了，你就可以从当前位置直接飞进大门了。
注意：瓷砖可以重复走过，但不能重复计数。输入格式
第一行两个正整数W和H，分别表示小路的宽度和长度。
以下H行为一个HxW的字符矩阵。每一个字符代表一块瓷砖。其中，代表安全的砖，＃代表不安全的砖，＠代表第一块砖。
输出格式
输出一行，只包括一个数，即你从第一块砖开始所能安全走过的最多的砖块个数（包括第一块砖）
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include<iostream> using namespace std; const int N=30; int n,m; // n行m列 char g[N][N]; bool st[N][N]; // 状态数组，记录每块瓷砖走过/没走过 int res=0; // 记录走过的瓷砖数 // 下面两个数组表示移动的方向(上右下左) int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; // 当前访问到的坐标是(x, y) void dfs(int x, int y) { for(int i = 0; i < 4; i++) { int tx = x + dx[i]; int ty = y + dy[i]; if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue; // 不能出界 if(g[tx][ty] != '.') continue; // 确保只走.而不走# if(st[tx][ty]) continue; // 确保每块瓷砖只走一次，避免重复计数 // 上面三行用于判断不走的条件 // 走(tx,ty)这个点 st[tx][ty] = true; res++; dfs(tx, ty); } } int main() { // 先读入地图 scanf("%d %d", &n, &m); for(int i = 0; i < n; i++) { scanf("%s", g[i]); } // 确定起始位置，找到@所在的位置 for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(g[i][j] == '@') { st[i][j] = true; dfs(i, j); } } } res++; printf("%d", res); return 0; }
题目五 水坑数量(迷宫类进阶)
题目描述
由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM（1≤N≤100，1≤M≤100）的网格图表示。每个网格中有水（w）或是旱地（．）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。
输入第1行：两个空格隔开的整数：N和M。
第2行到第N＋1行：每行M个字符，每个字符是w或．，它们表示网格图中的一排。字符之间没有空格。
输出一行，表示水坑的数量。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=110; int n,m; char g[N][N]; bool st[N][N]; int res=0; int dx[]={1,1,1,0,0,-1,-1,-1}; int dy[]={-1,0,1,1,-1,1,0,-1}; //不同与一般迷宫的四个方向，这道题八个方向都可以走 void dfs(int x,int y){ for(int i=0;i<8;i++){ int a=x+dx[i]; int b=y+dy[i]; if(a<0||a>=n||b<0||b>=m) continue; if(g[a][b]!='W') continue; if(st[a][b]) continue; st[a][b]=true; dfs(a,b); } } int main(){ scanf("%d %d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",g[i]); } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(g[i][j]=='W'&&!st[i][j]){ dfs(i,j); res++; } } } printf("%d",res); return 0; }
