当前位置:网站首页>搜素专题(DFS )
搜素专题(DFS )
2022-07-06 13:43:00 【Joanh_Lan】
搜素专题(DFS )
前言
搜素是一种暴力的方法
可以按照树去理解
在不剪支的情况下,可以把所有 *方案* “枚举”出来
剪支 --> 在确定一定不会是解的情况下,提前终止该"点"下面的搜素
类似树结构进行
一个问题可以被拆分成几个子部分去解决(有点DP的味道了,但本节课只是简单的搜索,方向食用)
换成人话来说:
如果把问题抽象成集合,每一个元素都可以看成一个局部的方案
所有 由一个个元素构成的子集 都可能会是问题的一个解
如果还有点晕
来一个实际的问题助助兴吧
123 这三个数全排列
图上每一个集合,都是问题的一个解
如:3 1 2
全排列实现代码
#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
bool st[N];
int ans[N];
int n;
void dfs(int cnt)
{
if (cnt == n)
{
for (int i = 1; i <= n; i++)
{
cout << ans[i];
cout << (i == n ? '\n' : ' ');
}
}
for (int i = 1; i <= n; i++)
{
if (!st[i])
{
ans[cnt + 1] = i;
st[i] = 1;
dfs(cnt + 1);
st[i] = 0;
}
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
ans[1] = i;
st[i] = 1;
dfs(1);
st[i] = 0;
}
}
int main()
{
solve();
}
模板
void dfs(需要使用的参数)
{
if(满足题意的条件)
{
xxx
}
if(边界条件 | 剪支)
{
xxx
return
}
灵活的dfs过程
根据题意书写,很灵活!
怎么舒服怎么来 (:
for (条件)
{
xxx
xxx
st[idx] = 1;//****
dfs(xxx)
st[idx] = 0//****
}
or
dfs(xxx)
等等
cout << ans << '\n';
}
题目
P2392 kkksc03考前临时抱佛脚
https://www.luogu.com.cn/problem/P2392
AC代码
#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int a[N];
int n1, n2, n3, n4;
int ans = 0, tt = 0;
int nn;
void dfs(int l, int r, int cnt)
{
if (cnt == nn)
{
tt = min(tt,max(l, r));
return;
}
dfs(l + a[cnt + 1], r, cnt + 1);
dfs(l, r + a[cnt + 1], cnt + 1);
}
void solve()
{
cin >> n1 >> n2 >> n3 >> n4;
for (int i = 1; i <= n1; i++)
cin >> a[i];
nn = n1, tt = 0x3f3f3f3f;
dfs(0, 0, 0);
ans += tt;
for (int i = 1; i <= n2; i++)
cin >> a[i];
nn = n2, tt = 0x3f3f3f3f;
dfs(0, 0, 0);
ans += tt;
for (int i = 1; i <= n3; i++)
cin >> a[i];
nn = n3, tt = 0x3f3f3f3f;
dfs(0, 0, 0);
ans += tt;
for (int i = 1; i <= n4; i++)
cin >> a[i];
nn = n4, tt = 0x3f3f3f3f;
dfs(0, 0, 0);
ans += tt;
cout << ans << endl;
}
int main()
{
solve();
}
P1135 奇怪的电梯
https://www.luogu.com.cn/problem/P1135
T代码
太过暴力,没有处理好重复的局部方案
换句话来说:剪支处理不到位
#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int s[N];
int n, bg, ed;
int ans = 0x3f3f3f3f;
void dfs(int idx, int cnt)
{
if (idx <= 0 || cnt > n)
return ;
if (idx == ed)
{
ans = min(ans, cnt);
return ;
}
dfs(idx + s[idx],cnt + 1);
dfs(idx - s[idx],cnt + 1);
}
void solve()
{
cin >> n >> bg >> ed;
for (int i = 1; i <= n; i++)
cin >> s[i];
dfs(bg,0);
cout << (ans == 0x3f3f3f3f ? -1 : ans) << '\n';
}
int main()
{
solve();
}
AC代码
#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int s[N];
int n, bg, ed;
int ans = 0x3f3f3f3f;
bool st[N];
void dfs(int idx, int cnt)
{
if (idx <= 0 || cnt > n || st[idx] || idx > n || cnt >= ans)
return ;
if (idx == ed)
{
ans = min(ans, cnt);
return ;
}
st[idx] = 1;
dfs(idx + s[idx],cnt + 1);
dfs(idx - s[idx],cnt + 1);
st[idx] = 0;
}
void solve()
{
cin >> n >> bg >> ed;
for (int i = 1; i <= n; i++)
cin >> s[i];
dfs(bg,0);
cout << (ans == 0x3f3f3f3f ? -1 : ans) << '\n';
}
int main()
{
solve();
}
本题の总结
1.标记的正确使用
2.剪支的判断 & 优化
...
计数类
P1605 迷宫
https://www.luogu.com.cn/problem/P1605
AC代码
#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int n, m, t;
int bgx, bgy, edx, edy;
int s[N][N];
bool st[N][N];
int xx[4] = {
0, 1, -1, 0}, yy[4] = {
1, 0, 0, -1};
int ans;
void dfs(int x, int y)
{
if (x == edx && y == edy)
{
ans++;
return;
}
for (int i = 0; i < 4; i++)
{
int tx = x + xx[i], ty = y + yy[i];
if ((tx >= 1 && tx <= n) && (ty >= 1 && ty <= m) && !s[tx][ty] && !st[tx][ty])
{
st[x][y] = 1;
dfs(tx, ty);
st[x][y] = 0;
}
}
}
void solve()
{
cin >> n >> m >> t;
cin >> bgx >> bgy >> edx >> edy;
for (int i = 1; i <= t; i++)
{
int a, b;
cin >> a >> b;
s[a][b] = 1;
}
dfs(bgx, bgy);
cout << ans << endl;
}
int main()
{
solve();
}
边栏推荐
- guava:创建immutableXxx对象的3种方式
- Four common ways and performance comparison of ArrayList de duplication (jmh performance analysis)
- Summary of cross partition scheme
- What about the spectrogram
- [Digital IC manual tearing code] Verilog automatic beverage machine | topic | principle | design | simulation
- 一行代码可以做些什么?
- 互联网快讯:吉利正式收购魅族;胰岛素集采在31省全面落地
- Redistemplate common collection instructions opsforzset (VI)
- Guava: three ways to create immutablexxx objects
- Realization of epoll reactor model
猜你喜欢
Fastjson parses JSON strings (deserialized to list, map)
Yyds dry goods inventory C language recursive implementation of Hanoi Tower
Digital transformation takes the lead to resume production and work, and online and offline full integration rebuilds business logic
一行代码可以做些什么?
[Chongqing Guangdong education] Information Literacy of Sichuan Normal University: a new engine for efficiency improvement and lifelong learning reference materials
MPLS experiment
[Li Kou brushing questions] one dimensional dynamic planning record (53 change exchanges, 300 longest increasing subsequence, 53 largest subarray and)
Leetcode topic [array] -118 Yang Hui triangle
Checkpoint of RDD in spark
【力扣刷题】一维动态规划记录(53零钱兑换、300最长递增子序列、53最大子数组和)
随机推荐
在最长的距离二叉树结点
First batch selected! Tencent security tianyufeng control has obtained the business security capability certification of the ICT Institute
Reptile practice (V): climbing watercress top250
Vit paper details
R3live notes: image processing section
【力扣刷题】一维动态规划记录(53零钱兑换、300最长递增子序列、53最大子数组和)
[Digital IC manual tearing code] Verilog automatic beverage machine | topic | principle | design | simulation
From campus to Tencent work for a year of those stumbles!
缓存更新策略概览(Caching Strategies Overview)
Search map website [quadratic] [for search map, search fan, search book]
Univariate cubic equation - relationship between root and coefficient
用aardio写一个旋转验证码标注小工具
Sql: stored procedures and triggers - Notes
3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
数字化转型挂帅复产复工,线上线下全融合重建商业逻辑
In JS, string and array are converted to each other (II) -- the method of converting array into string
WEB功能测试说明
MPLS experiment
Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
50个常用的Numpy函数解释,参数和使用示例