《算法竞赛从入门到国奖》算法基础:搜索-DFS初识
💡Yupureki:个人主页
🌸Yupureki🌸的简介:
目录
前言
DFS全称深度优先搜索，相当于是函数递归。其核心思想为"尽可能深"地搜索分支，直到遇到尽头再回溯
1. 选数
题目链接:
P1036 [NOIP 2002 普及组] 选数 - 洛谷
算法原理
对于每个数我们都有两种选择:选和不选
因此我们用dfs，枚举所有选择的情况，当选择的个数为3或没有数可选时返回
当然我们选择数也不是乱选，我们在dfs函数中添加一个参数pos，为从数组下标为pos的位置开始选数
由于要统计实时的选择的数的总和以及选择的个数，因此我们定义:
- sum为选择的数的总和
- cnt为选择的数的个数
- ret为总和为素数的结果
当cnt == 3时，判断sum是否为素数，因此要自己实现一个判断素数的函数
实操代码
#include <iostream> #include <vector> #include <cmath> using namespace std; vector<int> v; int n, k; int sum = 0; int cnt = 0; int ret = 0; bool isprime(int num)//判断是否为素数 { if (num <= 1)return false; if (num <= 3)return true; if (num % 2 == 0 || num % 3 == 0)return false; for(int i = 5; i <= sqrt(num);i++) { if (num % i == 0) return false; } return true; } void dfs(int pos)//从下标为pos的位置开始选数 { if (cnt == k) { if (isprime(sum)) ret++; return; } for (int i = pos; i < n; i++) { sum += v[i]; cnt++; dfs(i + 1); cnt--; sum -= v[i]; } return; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) { int num = 0; cin >> num; v.push_back(num); } dfs(0); cout << ret; return 0; }2. 飞机降落
题目链接:
P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷
算法原理
由于bfs是暴力枚举，因此使用bfs的前提是数据量不能大，一般10到20是合适的
而这个时候发现T小于或等于10，因此可以无脑使用bfs
我们枚举所有的飞机先后降落顺序的全排列，当安排完后进行判断:
- 如果无法正常降落，回退继续枚举
- 如果可以正常降落，直接退出bfs
当全排列的时候，每一次递归我们只能选择没有选过的飞机并且我们得全部选上，因此我们得用一个bool数组，来记录哪些飞机选了，哪些飞机没选
实操代码
#include <iostream> #include <vector> using namespace std; int n; vector<int> T; vector<int> D; vector<int> L; vector<int> ret; vector<bool> st;//飞机是否选中:true为选了;false为没选 bool check() { int time = T[ret[0]]; for (auto& it : ret) { int curtime = max(time,T[it]); if(curtime > T[it] + D[it]) return false; time = curtime + L[it]; } return true; } bool dfs() { if (ret.size() == n) { if (check()) { cout << "YES"<<endl; return true; } return false; } for (int i = 0; i < n; i++) { if (st[i] == false)//当飞机没选时，选上 { ret.push_back(i); st[i] = true; if (dfs()) return true; ret.pop_back(); st[i] = false; } } return false; } int main() { int group; cin >> group; while (group--) { T.clear(); D.clear(); L.clear(); st.clear(); ret.clear(); cin >> n; st.resize(n); for (int i = 0; i < n; i++) { int a, b, c; cin >> a >> b >> c; T.push_back(a); D.push_back(b); L.push_back(c); } if (dfs() == false) cout << "NO" << endl; } return 0; }3. 八皇后 Checker Challenge
题目链接:
P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷
算法原理
我们先一行一行地选择，每一行选择的情况必须满足以下条件:
- 每一列只有一个
- 每一条对角线只有一个
返回条件:
如果在一行发现没有可选的情况，则直接返回;
当最后一行选择完成后，就算这个选法是对的，随后记录下来
保证每一列只有一个是很好判断的，重点是如何判断对角线的情况
根据初中的平面直角坐标系，我们可以得到:两条对角线的方程
我们把两条直线x = 0和x = n分别当作每条对角线的映射关系:
y = -x + (i + j)打在x = 0上的点的集合表示该对角线的选择情况
y = x + (j - i)打在x = n上的带你的集合表示该对角线的选择情况
对应在数组中，即
- y[j- i + n] = true，表示y = x + (j - i)这条「主对角线」上放置了一个皇后;
- x[j + i] = true，表示y = -x + (i + j)这条「副对角线」上放置了一个皇后。
实操代码
#include <iostream> #include <vector> using namespace std; int n; int ret = 0; vector<int> v; vector<bool> st; vector<bool> x; vector<bool> y; void dfs() { if (v.size() == n) { ret++; if (ret <= 3) { for (auto& it : v) cout << it + 1 << " "; cout << endl; } return; } for (int i = 0; i < n; i++) { if (st[i] == false && x[i + v.size()] == false && y[i - v.size() + n] == false) { x[i + v.size()] = true; y[i - v.size() + n] = true; v.push_back(i); st[i] = true; dfs(); v.pop_back(); x[i + v.size()] = false; y[i - v.size() + n] = false; st[i] = false; } } return; } int main() { cin >> n; st.resize(n,false); x.resize(2 * n, false); y.resize(2 * n, false); dfs(); cout << ret; return 0; }
