搜索之DFS

一.搜索1.概念(暴力按照题目要求构造可能的答案对所有可能的答案进行枚举通过穷尽所有的可能来找最优解或者统计合法解的个数2.种类搜索分为DFS和BFS3.优化搜索有很多优化方式如减小状态空间更改搜索顺序剪枝等二.DFS1.DFS(图论深度优先搜索,是一种用于遍历或搜索树或图的算法。所谓深度优先就是说每次都尝试向更深的节点走2.搜索之DFS在搜索算法 中该DFS常常指利用递归函数方便地实现暴力枚举的算法与图论中的 DFS 算法有一定相似之处但并不完全相同。3.特点通常是构造一棵搜索树或说是状态树图来进行搜索。4.基础模板void dfs(int n) { //1.终止条件 //2.dfs(int n) //3.回溯 }三.例题1.https://www.luogu.com.cn/problem/P1706分析样例以N3为例构造一棵搜索树或说是状态树来进行搜索。同时用数组来存放搜索树中的结果。 思路 先定义两个数组一个是用来存放合法解一个是用来标记该数是否用过。 我们可以先写一个用于打印的函数print()每当深搜时找到一个符合条件的解时则输出一下输出这个解注意题目输出格式--5个场宽。 接下来就是写基于递归的深搜函数了。主要思路先判断格子是否填满了如果填满则print()一下。如果没有填满则开始循环在循环中先判断当前填的数是否用过如果没有则填入搜索下一格。需要回溯 回溯就是要消除搜索过程中的不同可能性之间对中间变量的影响,即搜索下一个答案之前保证上一个答案对下一个答案没影响恢复到之前的状态代码如下时间复杂度是On#includebits/stdc.h using namespace std; #define int long long #define endl \n int n; int ans[10];//记录每一位的答案 int flag[10];//记录该数字是否被选取 void dfs(int x) {//选取第x个数-给第x个位置填数 //1.终止条件 if (xn) {//n个位置填满了 输出一个答案 for (int i1;in;i) { coutsetw(5)ans[i]; } coutendl; return; } //2.dfs(int n) for (int i1;in;i) {//枚举所有可以填的数 if (flag[i]0) {//i没有被用过 ans[x]i;//i填到x位置 flag[i]1;//标记已用 dfs(x1);//继续填下一个位置 //3.回溯 flag[i]0;//继续考虑其他选择把i变成其他位置可用的状态---回溯----撤销本层所做的一些事 } } } void solve() { cinn; dfs(1); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t 1; //cin t; while (t--) { solve(); } }注意在搜索算法中DFS也常被用于在网格中搜索。搜索过程中考虑往4个或者8个方向搜索同时要注意不要越过网格的边界。2.200. 岛屿数量 - 力扣LeetCode​​​​​​思路 主循环遍历整个矩阵。当遇到一点为‘1’时说明遇到了一个岛屿岛屿数目1。但是这个‘1’只是岛屿的一部分所以要通过 DFS来搜索到整个岛屿并把这个岛屿的值全改为0防止重复计算答案。 DFS设目前在i,j点搜索ij所在的整个岛屿。从ij向上下左右四个方向进行搜索 i1,j(i-1,j) (i,j-1) (i,j1)。若这4个点为‘1’且不越界则可以走过去然后将走到的点的值改为‘0’再以走到的点为基础进行搜索代码如下时间复杂度Om*n#includebits/stdc.h using namespace std; #define int long long #define endl \n int n,m; void dfs(vectorvectorchar grid,int i,int j) {//当前位置为陆地 int ngrid.size(); int mgrid[0].size(); //把grid[i][j]变为海洋 grid[i][j]0; //向上走 if (i-10 grid[i-1][j]1)dfs(grid,i-1,j); //向下走 if (i1n grid[i1][j]1)dfs(grid,i1,j); //向左走 if (j-10 grid[i][j-1]1)dfs(grid,i,j-1); //向右走 if (j1m grid[i][j1]1)dfs(grid,i,j1); } int numIslands(vectorvectorchar grid){ int ngrid.size(); int mgrid[0].size(); int cnt0; for(int i0;in;i) { for(int j0;jm;j) { if(grid[i][j]1) { cnt; dfs(grid,i,j); } } } return cnt; } void solve() { vectorvectorchar grid(n,vectorchar(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int ansnumIslands(grid); cout ans endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t 1; //cin t; while (t--) { solve(); } }各位道友若有疑问评论区留言