本文主要是介绍【万题详解】DFS搜索专题合集（中），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
课前C++小程序（关机，休眠，注销程序）
有的时候我们需要让电脑在一段时间工作而不能关机，但是工作完成之后不关机会造成用电浪费，那么使用自动关机命令，就不用担心电脑一直开着会浪费电啦。夜里看电影，双眼迷离睁不开，不想去关机，有个自动关机多好啊！下载资料电影音乐，有需要出门或者夜深需要休息，估计一些下载时间，设置个定时自动关机吧！下班了，资料没传完，不要紧，设置个定时自动关机，放心下班！这些都不是问题，只需几步，多种情况都搞定！
当然我们不能简单的关机（win+电源+关机），我打算用C++。
C++关机……代码:
//1、直接关机
#include <windows.h>
int main()
{system ("shutdown -p");retrun 0;
}
//2、30秒后关机
//#include <windows.h>
//int main()
//{
// system ("shutdown -s");
//}
//3、自定义时间后关机
//#include <windows.h>
//int main()
//{
// system ("shutdown -s -t 180"); // 180是秒数，这里是三分钟后关机
//}
//4、深度休眠
//#include <windows.h>
//int main()
//{
// system ("shutdown -h");
//}
//5、注销
//#include <windows.h>
//int main()
//{
// system ("shutdown -l");
//}
//6、取消关机计划
//#include <windows.h>
//int main()
//{
// system ("shutdown -a");
//}正片开始
上一次讲了【万题详解】DFS搜索专题合集（上）-CSDN博客，今天来讲讲其他DFS搜索题目。
提示
不会用洛谷的可以看看这篇文章——洛谷使用指南
还有，以下链接是题目的链接。
1.迷宫 - 洛谷
2.魔术数字游戏 - 洛谷
3.[COCI2008-2009 #2] PERKET - 洛谷
4.kkksc03考前临时抱佛脚 - 洛谷
P1605 迷宫
给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 N,M,T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数SX,SY,FX,FY，SX,SY 代表起点坐标，FX,FY 代表终点坐标。
接下来 T 行，每行两个正整数，表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
输入输出样例
输入 #1
2 2 1 1 1 2 2 1 2输出 #1
1对于 100% 的数据，1≤N,M≤5，1≤T≤10，1≤SX,FX≤n，1≤SY,FY≤m。
解题思路
这题除了深搜，还是深搜。
深搜，一句话来总结一下，就是：
不撞南墙不回头
而在这题里，“南墙”有三个：
第一个是真墙：迷宫的围墙
也就是俗话所说的越界。越界了你还不回头，你是想去哪儿？
第二个是山墙:障碍物T
如果T横在你面前，你还是绕路吧！
第三个是人造墙：题目说了每个方格最多只能走一次
这是真没办法
所以深搜的返回条件就出来了——就是以上那三堵墙
我们每次可以从上下左右四个方向进行深搜，一旦遇上南墙就返回，如果走到了重点，s++。
记住了，题目里说保证起点没有障碍，并没有保证终点也没有啊！
AC
#include<iostream>
using namespace std;
int n, m, t, sx, sy, fx, fy;
int vis[10][10]; //标记
int mp[10][10]; //障碍物位置
int ans = 0;
int xx[] = { 1,0,-1,0 };
int yy[] = { 0,-1,0,1 };
void dfs(int x, int y)
{if (x == fx && y == fy){ans++;return;}for (int i = 0; i < 4; i++){int dx = xx[i] + x;int dy = yy[i] + y;if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && vis[dx][dy]==0 && mp[dx][dy]==0){vis[dx][dy] = 1;dfs(dx, dy);vis[dx][dy] = 0;}}
}
int main()
{cin >> n >> m >> t >> sx >> sy >> fx >> fy;while (t--){int a, b;cin >> a >> b;mp[a][b] = 1;}vis[sx][sy] = 1;dfs(sx, sy);cout << ans << endl;return 0;
}P1274 魔术数字游戏
题目描述
填数字方格的游戏有很多种变化，如下图所示的 4×4 方格中，我们要选择从数字 1 到 16 来填满这十六个格子(Ai,j ，其中 i=1⋯4 ，j=1⋯4)。为了让游戏更有挑战性，我们要求下列六项中的每一项所指定的四个格子，其数字累加的和必须为34 ：
A1,1
A1,2
A1,3
A1,4
A2,1
A2,2
A2,3
A2,4
A3,1
A3,2
A3,3
A3,4
A4,1
A4,2
A4,3
A4,4
四个角落上的数字，即 A1,1+A1,4+A4,1+A4,4=34 。
每个角落上的 2×2 方格中的数字，例如左上角 A1,1+A1,2+A2,1+A2,2=34 。
最中间的 2×2方格中的数字，即 A2,2+A2,3+A3,2+A3,3=34 。
每条水平线上四个格子中的数字，即 Ai,1+Ai,2+Ai,3+Ai,4=34，其中 i=1⋯4 。
每条垂直线上四个格子中的数字，即 j+A2,j+A3,j+A4,j=34，其中 j=1⋯4 。
两条对角线上四个格子中的数字，例如左上角到右下角 1+A2,2+A3,3+A4,4=34 。
右上角到左下角：A1,4+A2,3+A3,2+A4,1=34 。
特别的，我们会指定把数字 1 先固定在某一格内。
输入格式
输入只有一行包含两个正数据 i 和 j ，表示第 i 行和第 j 列的格子放数字 1。剩下的十五个格子，请按照前述六项条件用数字 2 到 16 来填满。
输出格式
输出四行，每行四个数，相邻两数之间用一个空格隔开，并且依序排好。排序的方式，是先从第一行的数字开始比较，每一行数字，由最左边的数字开始比，数字较小的解答必须先输出到文件中。
输入输出样例
输入 #1
1 1
输出 #1
1 4 13 16
14 15 2 3
8 5 12 9
11 10 7 6说明/提示
样例的另一种方法是：
1 4 13 16 14 15 2 3 12 9 8 5 7 6 11 10可以得到，对于样例，合理的填写方法有 216 种，以上仅为其中的两种。
数据规模与约定
对于全部的测试点，保证 1≤i,j≤4。
解题思路
因为题目信息给的太多，4*4以及很多和要为34，剪枝很好剪，我就直接开挂对每个位置特判一下。比如说在(1,4)的时候检查第一行是否为34，在(1,4)时检查第一列的和和对角线的和。然后在调试的时候我发现，对于样例中(1,1)为1的情况 第一列会是这样：
第一次:1 2 2 X 返回
第二次:1 2 3 X 返回我觉得我是该做点什么来阻止这愚蠢的行为了。于是我在每个要求的区域和为34的第三个点特判，先把前两个的和算出来，（当前要填的为i）
i=max(i,34-mx[1][2]-mx[1][1]-16);
if(i>16) return ;
意思应该很好懂，这是(1,3)处的特判。然后我又发现这一列的和明明前三个就已经大于34了还在搜, = =,真是看不下去了。于是对于每个搜到的点计算列之和还有行之和，大于34直接return。看来效果好像不错的样子，最慢的一个点0.2s。
AC
#include<bits/stdc++.h>
using namespace std;
int n,m,a[11][11],f[101],g[11],d=0;
void s(int x,int y) {if(x==4&&y>4) { for(int i=1; i<=4; i++) {for(int j=1; j<=4; j++) if(j==4) cout<<a[i][j]<<endl;else cout<<a[i][j]<<" ";}cout<<endl;}if(y>4) { int z=0;for(int i=1; i<=4; i++) z+=a[x][i];if(z==34) s(x+1,1);return;}if(x==n&&y==m) { s(x,y+1);return;}for(int i=2; i<=16; i++) if(f[i]==0) { if(x==4) { int z=i;for(int j=1; j<=3; j++) z+=a[j][y];if(z!=34) continue;}if(x==4&&y==4) {int z=i+a[1][1]+a[4][1]+a[1][4];if(z!=34) continue;}if(x==4&&y==1) { int z=i+a[1][4]+a[2][3]+a[3][2];if(z!=34) continue;}if(x==4&&y==4) { int z=i+a[1][1]+a[2][2]+a[3][3];if(z!=34) continue;}if(x==3&&y==3) { int z=i+a[2][2]+a[2][3]+a[3][2];if(z!=34) continue;}if(x==2&&y==2) { int z=i+a[1][1]+a[1][2]+a[2][1];if(z!=34) continue;}if(x==2&&y==4) { int z=i+a[1][3]+a[1][4]+a[2][3];if(z!=34) continue;}if(x==4&&y==2) { int z=i+a[3][1]+a[3][2]+a[4][1];if(z!=34) continue;}if(x==4&&y==4) { int z=i+a[3][3]+a[3][4]+a[4][3];if(z!=34) continue;}f[i]=1;a[x][y]=i;s(x,y+1);f[i]=0;}
}
int main() {cin>>n>>m;a[n][m]=1;f[1]=1;s(1,1);return 0;
}
P2036 [COCI2008-2009 #2] PERKET
题目描述
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
输入格式
第一行一个整数 n，表示可供选用的食材种类数。
接下来 n 行，每行 22 个整数 si 和 bi，表示第 i 种食材的酸度和苦度。
输出格式
一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
输入输出样例
输入 #1
1
3 10输出 #1
7
输入 #2
2
3 8
5 8输出 #2
1
输入 #3
4
1 7
2 6
3 8
4 9输出 #3
1
说明/提示
数据规模与约定
对于 100%的数据，有 1≤n≤10，且将所有可用食材全部使用产生的总酸度和总苦度小于 1×109，酸度和苦度不同时为 1 和 0。
说明
本题满分 7070 分。
题目译自 COCI2008-2009 CONTEST #2 PERKET，译者 @mnesia。
附件下载
contest2_tasks.pdf101.88KB
解题思路
外面用一个for循环来代表选取材料的数量，将这个数量当做参数。
然后，说一下坑点：
这个题目要看清了，我们知道它们各自的酸度S和甜度B。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的甜度为每一种配料的甜度的总和。
然后，我们必须添加至少一种配料。
最后，有几个方法给初学者讲一下：
1、ios::sync_with_stdio(false);这个方法还是要解释一下的
在某些题目中，我们使用普通的cin和cout会超时，所以我们每次只能打scanf和printf，然后一堆的占位符巨麻烦），为什么cin和cout比scanf和printf用的时间多？
这是因为C++中，cin和cout要与stdio同步，中间会有一个缓冲，所以导致cin，cout语句输入输出缓慢，这时就可以用这个语句，取消cin，cout与stdio的同步，说白了就是提速，效率基本与scanf和printf一致。
2、abs绝对值
abs 是 absolute value （绝对值）缩写。c++ 中的一个数学函数，计算整型量的绝对值。要头文件 #include <cmath> 或 #include <math.h>
算例：
int x=16, y= -6;
cout << abs(x) << endl;
cout << abs(y) << endl;
输出：
16
6
但是注意浮点数要使用fabs
3、min取最小值
例如：
int a=10,b=8;
cout<<min(a,b);则这段代码会输出8AC
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
long long ans = 1e8;
int s[N], b[N];
void dfs(long long sd, long long kd, int str)
{int t = abs(sd - kd);if(str != 0 && t < ans) ans = t;//不是第一次进入才比较ans和t，因为第一次进入sd - kd为0，则ans一直为0，是错误的for(int i = str; i < n; i ++)if(sd == 0 && kd == 0) dfs(s[i], b[i], i + 1);//第一次需要特判一下，因为存在sd = 0乘任何数都是0了，但kd是能加的else dfs(sd * s[i], kd + b[i], i + 1);//i + 1是起始位置
}int main ()
{cin >> n;for(int i = 0; i < n; i ++) cin >> s[i] >> b[i];dfs(0, 0, 0);cout << ans;return 0;
}
P2392 kkksc03考前临时抱佛脚
题目背景
kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。
题目描述
这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等A1,A2,…,As1，B1,B2,…,Bs2，3C1,C2,…,Cs3，D1,D2,…,Ds4）。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 2道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入格式
本题包含 5 行数据：
第 1 行，为四个正整数 s1,s2,s3,s4。
第 2行，为 A1,A2,…,As1 共 s1 个数，表示第一科习题集每道题目所消耗的时间。
第 3 行，为 B2,…,Bs2 共 s2 个数。
第 4 行，为 C1,C2,…,Cs3 共 s3 个数。
第 5 行，为 D1,D2,…,Ds4 共 s4 个数，意思均同上。
输出格式
输出一行,为复习完毕最短时间。
输入输出样例
输入 #1
1 2 1 3
5
4 3
6
2 4 3输出 #1
20
说明/提示
1≤s1,s2,s3,s4≤20。
1≤A1,A2,…,As1,B1,B2,…,Bs2,C1,C2,…,Cs3,D1,D2,…,Ds4≤60。
解题思路
这道题可以运用dp方法求解，建议与P1489 猫狗大战配合食用，效果更佳。（P1489 猫狗大战会在下一个题目讲解里出现，敬请期待）
这道题的目的就是将每一科目的所有数分成两部分，使得两部分的差最小。
首先，对于每一科目，用布尔类型数组f[i][j]表示i个数中取得总和j是否可行，可行则为true，否则为false。
显然，初始化使得f[0][0]=1.
本题的输入数据可以用二维数组来存储，那么状态转移方程可以表示为:f[j][k]=f[j][k]||f[j-1][k-a[t][i]] 然后我们可以从sum[t]>>1开始枚举，若f[j]i为true，则答案为max(i,sum[t]-i)，退出函数即可。
将以上过程重复四次，累加所得答案，输出andAC！
AC
#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,k,sum,t,homework[21],dp[2501];
int main(){for(i=1;i<=4;i++)cin>>a[i];for(i=1;i<=4;i++){sum=0; for(j=1;j<=a[i];j++){cin>>homework[j];sum+=homework[j];}for(j=1;j<=a[i];j++)for(k=sum/2;k>=homework[j];k--)dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);t+=sum-dp[sum/2];for(j=1;j<=sum/2;j++)dp[j]=0;}cout<<t;return 0;
}
结尾
希望大家多多关注！！！
如果你能支持一下我，我十分感谢！！！
如果有人想在洛谷上做题，可以点下方链接：
https://www.luogu.com.cn/
如果你喜欢或想了解一下其他的算法，可以看看以下这些：
洛谷指南
洛谷使用指南_洛谷怎么看-CSDN博客
题目详解系列（部分）：
【万题详解】DFS搜索专题合集（上）-CSDN博客
【万题详解】P1314 [NOIP2011 提高组] 聪明的质监员-CSDN博客
【万题详解】洛谷P1282 多米诺骨牌-CSDN博客
【万题详解】洛谷P1238 走迷宫-CSDN博客
【万题详解】洛谷P1135奇怪的电梯-CSDN博客
【万题详解】洛谷P1510 精卫填海-CSDN博客
【万题详解】洛谷P1252 马拉松接力赛-CSDN博客
【万题详解】洛谷P1359 租用游艇-CSDN博客
【百题详解】洛谷P8508 做不完的作业-CSDN博客
【万题详解1】洛谷P1230 智力大冲浪-CSDN博客
【全网首发】洛谷贪心题解合集2-CSDN博客
【全网首发】洛谷贪心题解集合-CSDN博客
洛谷二分题集（3题）-CSDN博客
游戏系列：
C++棋类小游戏2-CSDN博客
C++自创棋类小游戏-CSDN博客
C++：史上最坑小游戏-CSDN博客
C++：自创小游戏-CSDN博客
C++：下雪-CSDN博客
C++讲解系列（算法）：
C++：第十五讲高精度算法-CSDN博客
C++：第十四讲动态规划初步-CSDN博客
C++：第十三讲BFS广度优先搜索-CSDN博客
C++:第十二讲DFS深搜（二）_c++匿名函数dfs-CSDN博客
C++：第十一讲DFS深搜-CSDN博客
C++：第十讲二分查找-CSDN博客
前缀和与差分：
C++：第九讲前缀和与差分-CSDN博客
贪心：
C++：第八讲贪心算法1-CSDN博客
C++讲解系列（基础入门）：
排序：
C++：第七讲冒泡排序-CSDN博客
函数：
C++第6讲max和min函数_c++ min函数-CSDN博客
C++第五讲函数初步-CSDN博客
for循环&数组：
C++第四讲for循环及数组-CSDN博客
if语句&else语句及运算：
C++第三讲：C++中的逻辑运算符及if else语句-CSDN博客
基础：
C++第二讲输入与输出-CSDN博客
C++第一讲认识C++编译器-CSDN博客
欢迎收看，希望大家能三连！
最后认识一下，我是爱编程的喷火龙廖，我们有缘再见！
这篇关于【万题详解】DFS搜索专题合集（中）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
