搜索

搜索，常常适用于当我们想不出题目正解时所采取所谓的骗分方法，因为题目很大部分搜索是会过不了$100\%$样例的,但是由于搜索的思维简单和暴力性，我们往往可以较为轻松的骗到很大一部分分数。

dfs(深度优先搜索)

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。
该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。
DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样。

顾名思义，深度优先搜索就是要我们一层一层的去遍历访问，进行决策直到达到临界条件。
dfs代码和递归类似，但是其思想不一样

1
2
3
4
5
6
7
8
9
#模板
void dfs(int x)
{
    if(x == 临界条件)return;
    if(条件)
    {
        dfs(x + 1);//下一步
    }
}

例题:[luoguP1706]全排列问题
思路:从第一个位开始讨论遍历,对于每一位，for循环探讨每一个数字，如果这个数字没被之前几位用过那么我们就将他作为这一位的答案

info 注意，这里需要用到回溯的思想，即这一种情况全部讨论完当需要讨论下一种情况时，需将当前标记过的状态还原，代码实现也非常简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#参考代码
#include <bits/stdc++.h>
using namespace std;
int n,vis[11],ans[11];
void dfs(int k){
	if(k>n){
		for(int i=1;i<=n;i++){
			printf("%5d",ans[i]);
		}
		cout<<endl;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			vis[i]=1; //标记已经用过
			ans[k]=i; //加入答案
			dfs(k+1); //遍历下一位
			vis[i]=0; //回溯思想
		}
	}
}
int main(){
	cin>>n;
	dfs(1); //遍历第一位
	return 0;
}

练习题:[luoguP1219]八皇后 -> 也是dfs加回溯的思想