莱芜警方网站官网_营销方案案例_seo网络推广培训班_郑州网站推广公司哪家好

搜索

DFS基础+回溯

回溯法简介：

回溯法一般使用DFS（深度优先搜索）实现，DFS是一种遍历或搜索图、树或图像等数据结构的算法，当然这个图、树未必要存储下来（隐式处理就是回溯法），常见的是通过某种关系构造出的搜索树，搜索树一般是排列型搜索树（总节点个数一般为n！级别）和子集型搜索树（总节点个数一般为2^n级别）。

排列型就是每次枚举选哪个，子集型就是对于每一个元素选或不选（结果与顺序无关）

DFS从起始节点开始，沿着一条路径尽可能深入地搜索（一条路走到黑），直到无法继续为止，然后回溯到前一个节点，继续探索其他路径，直到遍历完整个图或树。
DFS使用栈或递归来管理节点的遍历顺序，一般使用递归。
很多时候DFS和回溯法不必过度区分。

排列树

子集树

回溯法模板

这是一个排列型搜索树，实际上的回溯法比较灵活，需要根据题意要求来具体分析。
visll表示数字i是否使用过，也经常被用于表示某个元素是否使用过。
all存放结果，当dep深度=n + 1时说明n层都已经算完了，直接输出结果。
子集型搜索树模板结构类似，就是在往下走时候只有两条边，表示“选或不选当前这个元素”。

eg1——N皇后问题

 代码：

#include<bits/stdc++.h>
using namespace std;
int a[11][11];
int ans = 0; int n;
bool check(int deep,int m){for(int k = 0; k < n ; ++ k){if(a[k][m]) return false;}// 检查所有方向以判断皇后是否会攻击//下方还没有放置皇后，所以不用检查for(int i = 1; i <= deep; i++) {if(a[deep - i][m]) return false; // 检查上方if(m - i >= 0 && a[deep - i][m - i]) return false; // 检查左上方if(m + i < n && a[deep - i][m + i]) return false; // 检查右上方}return true;
}
void dfs(int deep){if(deep == n){ans++;return;}for(int i = 0; i < n ; ++ i){if(check(deep,i)){a[deep][i] = 1; // 放置皇后dfs(deep+1);a[deep][i] = 0; // 移除皇后}}
}
int main(){cin>>n;dfs(0);cout<<ans;return 0;
}    

eg2——小朋友的崇拜圈

#include<stdio.h>
int n;
int a[100001],v[100001];
int max=0;//定义全局变量，方便求最大值
int t;//暂时保存开始位置的小朋友的编号void dfs(int x,int y)
{if(v[x])//只要访问过了已经访问的编号，就是有闭合的圈{if(a[x]==a[t])//只有满足这个条件，才符合一个真正意义上的圈{if(y>max)max=y;}return;}else{v[x]=1;dfs(a[x],y+1);v[x]=0;//每次进行一次dfs搜索，回溯，避免影响下一次的搜索}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)//这个开始的编号要从1开始比较方便，因为每个人崇拜的小朋友的编号都是从下标为1开始的{t=i;//t暂时保存此时的为起点的小盆友的编号dfs(i,0);//每个小朋友都进行一次dfs搜索}printf("%d",max);return 0;
}

eg3——全球变暖

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e3 + 10, M = N * N;char g[N][N];
int n, ans, vis[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool flag = true;  // 假设被淹没void has_submerge(int sx, int sy)
{vis[sx][sy] = 1;bool has_water = false;  // 假设周围没有水for(int i = 0; i < 4; i++)  // 遍历四个方向{int x = sx + dx[i], y = sy + dy[i];if(x < 0 || y < 0 || x >= n || y >= n) continue;if(vis[x][y] ) continue;if(g[x][y] == '.'){ has_water = true; continue;}vis[sx][sy] = 1;has_submerge(x, y);}if(!has_water) flag = false;  // 四个方向循环完再去更新flag 
}
int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> g[i];for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)if(g[i][j] == '#' && !vis[i][j]){flag = true;has_submerge(i, j);if(flag) ans ++;}cout << ans << endl;return 0;
}

 

 eg4——数字王国之军训排队

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int a[N];
vector<int> vec[N];//二维vector这样定义，别用vector<vector<int>> vec,因为前者外部vector已声明大小，可以直接调用迭代器，后者不行 
bool dfs(int dep,int i)//dep为第几个学生，i为分几队 
{//dfs用于判断是否可以分为i队 if(dep==n+1) return true;//如果递归到了最底层，说明可以分成i队 for(int j=0;j<i;j++)//将当前dep学生分到j队 {    bool flag=false;for(const auto &b:vec[j]) //遍历二维vector，遍历vector用auto枚举比较方便， {//这种题型与组合枚举不一样，不要用两条件来思考 if(a[dep]%b==0) //如果当前将要入队的数字学生与队里面的数字可以整除，即有倍数关系 {                 //因为用sort排过序，所以a[dep]一定比b大 flag=true;break;}}if(flag) continue;vec[j].push_back(a[dep]);if(dfs(dep+1,i)) return true;//不要写成return true，布尔dfs的递归这样写，若为false仍需执行后面的恢复现场语句 //恢复现场 vec[j].pop_back();}return false; //中间执行完后没有return true，则return false 
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<=n;i++)//将1到n队都试试 {if(dfs(1,i)) //第一个可行的队即为最少的队 {cout<<i;break;}}return 0;
}

eg5——特殊的三角形