搜索之DFS
一.搜索
1.概念(暴力）：按照题目要求构造可能的答案，对所有可能的答案进行枚举，通过穷尽所有的可能来找最优解，或者统计合法解的个数
2.种类：搜索分为DFS和BFS
3.优化：搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等
二.DFS
1.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
分析样例：以N=3为例，构造一棵搜索树（或说是状态树）来进行搜索。同时用数组来存放搜索树中的结果。 思路： 先定义两个数组，一个是用来存放合法解，一个是用来标记该数是否用过。 我们可以先写一个用于打印的函数print()，每当深搜时找到一个符合条件的解时，则输出一下，输出这个解（注意题目输出格式--5个场宽）。 接下来就是写基于递归的深搜函数了。主要思路：先判断格子是否填满了，如果填满，则print()一下。如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填入，搜索下一格。（需要回溯） 回溯就是要消除搜索过程中的不同可能性之间对中间变量的影响,即搜索下一个答案之前，保证上一个答案对下一个答案没影响，恢复到之前的状态
代码如下：时间复杂度是O（n！）
#include<bits/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 (x>n) {//n个位置填满了 输出一个答案 for (int i=1;i<=n;i++) { cout<<setw(5)<<ans[i]; } cout<<endl; return; } //2.dfs(int n) for (int i=1;i<=n;i++) {//枚举所有可以填的数 if (flag[i]==0) {//i没有被用过 ans[x]=i;//i填到x位置 flag[i]=1;//标记已用 dfs(x+1);//继续填下一个位置 //3.回溯 flag[i]=0;//继续考虑其他选择，把i变成其他位置可用的状态--->回溯---->撤销本层所做的一些事 } } } void solve() { cin>>n; 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）点，搜索（i，j）所在的整个岛屿。从（i，j）向上下左右四个方向进行搜索 （i+1,j）(i-1,j) (i,j-1) (i,j+1)。若这4个点为‘1’，且不越界，则可以走过去，然后将走到的点的值改为‘0’，再以走到的点为基础进行搜索
代码如下：时间复杂度O（m*n）
#include<bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int n,m; void dfs(vector<vector<char>>& grid,int i,int j) {//当前位置为陆地 int n=grid.size(); int m=grid[0].size(); //把grid[i][j]变为海洋 grid[i][j]='0'; //向上走 if (i-1>=0 && grid[i-1][j]=='1')dfs(grid,i-1,j); //向下走 if (i+1<n && grid[i+1][j]=='1')dfs(grid,i+1,j); //向左走 if (j-1>=0 && grid[i][j-1]=='1')dfs(grid,i,j-1); //向右走 if (j+1<m && grid[i][j+1]=='1')dfs(grid,i,j+1); } int numIslands(vector<vector<char>>& grid){ int n=grid.size(); int m=grid[0].size(); int cnt=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(grid[i][j]=='1') { cnt++; dfs(grid,i,j); } } } return cnt; } void solve() { vector<vector<char>> grid(n,vector<char>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; } } int ans=numIslands(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(); } }各位道友若有疑问，评论区留言