DFS 与 BFS
DFS
定义： 深度优先搜索（DFS）是一种以深入探索图的分支为目标，直到到达指定的“深度”，无法继续前进为止，然后通过回溯探索其他分支。
用途：
- 通过枚举的方式来遍历当前的所有状态
- 搜索图或者树
例如：解决迷宫问题，路径查找、检查图中是否存在环、排序问题等。
优点
- 空间复杂度较低
缺点
- 时间复杂度可能高：在最坏的情况下，需要遍历所有的情况
全排列
DFS入门。
- 通过枚举每一个位置可以放置的数字来枚举每一种排列
- 放置后标记这个数表示已经放过了
- 当排列中的元素都被标记后，输出结果
- 时间复杂度:
#include<bits/stdc++.h>
using namespace std;
int n,vis[10],ans[10];
void dfs(int x){
if(x==n+1){
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<'\n';
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
ans[x]=i;
vis[i]=1;
dfs(x+1);
vis[i]=0;
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
组合
- 从n个数中选取m个数
- 满足前一个数比后一个数小
- 同全排列一样枚举，注意不用标记，再加上判断last,表示上一个数是多少。
- 最后统计答案
#include<bits/stdc++.h>
using namespace std;
int n,vis[10],ans[10];
int m;
void dfs(int x,int last){
if(x==m+1){
for(int i=1;i<=m;i++){
cout<<ans[i]<<" ";
}
cout<<'\n';
return;
}
for(int i=last+1;i<=n;i++){
ans[x]=i;
dfs(x+1,i);
}
}
int main(){
cin>>n>>m;
dfs(1,0);
return 0;
}
子集枚举
- 一个为1~n的序列中取出所有子集
- 考虑枚举每一个位置选与不选
- 当枚举的上限达到n+1时输出结果
#include<bits/stdc++.h>
using namespace std;
int n,vis[10],ans[10];
int cnt=0;
void dfs(int x){
if(x<=n+1){
ans[++cnt]=x;
dfs(x+1);
--cnt;
dfs(x+1);
}
else{
for(int i=1;i<=cnt;i++){
cout<<ans[i]<<" ";
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
走迷宫类问题
- 从（fx,fy）到达（zx,zy）的不重复合法路径的数量
- 枚举每个点向四个方向走，直到无法走，边走边标记
- 最后到达终点答案加一，返回。
#include<bits/stdc++.h>
using namespace std;
int n,m,t,vis[10][10],sx,sy,fx,fy,num;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y){
if(x==fx&&y==fy){
num++;
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(!vis[nx][ny]&&nx>=1&&nx<=n&&ny>=1&&ny<=m){
vis[nx][ny]=1;
dfs(nx,ny);
vis[nx][ny]=0;
}
}
}
int main(){
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
while(t--){
int a,b;
cin>>a>>b;
vis[a][b]=1;
}
vis[sx][sy]=1;
dfs(sx,sy);
cout<<num;
return 0;
}
剪枝
在搜索过程中，提高效率，减少不必要的搜索的方法，通常有以下四种方法
- 最优性剪枝 ： 顾名思义，当当前的答案比现在正在搜索的答案更优时，直接返回
- 可行性剪枝 ： 当当前遍历到的的方案不合法，直接返回
- 搜索顺序剪枝 ： 改变搜索的顺序，从已知信息多的地方开始搜索可能更加快速
- 排除等效冗余 ： 可以通过记忆化搜索的方式，把已知或者等同于先前某种答案的答案直接返回。
最终挑战：小木棍
BFS
- BFS 全称是 Breadth First Search，宽度优先搜索，也叫广度优先搜索。
- 一般通过把当前这一步所能到达的所有的地方加入队列，以此来加快效率
- BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。
- 在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问，也是最优的
例题：
马的遍历
- 从起点开始把每一步可能到达的点加入队列
- 挂上最小值
- 统计答案
#include<bits/stdc++.h>
#include<queue>
#define int long long
using namespace std;
struct Node{
int x,y;
};
int n,m;
bool vis[410][410];
queue<Node>q;
Node node;
int dx[8]={-1,-2,1,2,-1,-2,1,2};
int dy[8]={2,1,2,1,-2,-1,-2,-1};
int fx,fy;
int ans[410][410];
void bfs(int x,int y){
q.push({x,y});
while(q.size()){
Node nd=q.front();q.pop();
for(int i=0;i<8;i++){
int nx=nd.x+dx[i];
int ny=nd.y+dy[i];
if(nx>=1&&ny<=m&&nx<=n&&ny>=1&&(!vis[nx][ny])){
// cout<<nx<<' '<<ny<<'\n';
vis[nx][ny]=1;
ans[nx][ny]=ans[nd.x][nd.y]+1;
q.push({nx,ny});
}
}
}
}
signed main(){
cin>>n>>m>>fx>>fy;
memset(ans,-1,sizeof(ans));
ans[fx][fy]=0;
vis[fx][fy]=1;
bfs(fx,fy);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cout<<ans[i][j]<<" ";
cout<<'\n';
}
return 0;
}
血色先锋队
- 把每一个起点（感染源）开始，向外扩散；
- 枚举四个方向
- 加入队列
- 统计答案
#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int n,m,a,b;
int vis[501][501],ans[5000][5000];
struct Node{
int x,y;
};
queue<Node>q;
Node node;
void bfs(){
q.push(node);
while(!q.empty()){
Node nd=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=nd.x+dx[i];
int ny=nd.y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]){
Node tmp;
tmp.x=nx;tmp.y=ny;
q.push(tmp);
ans[nx][ny]=ans[nd.x][nd.y]+1;
vis[nx][ny]=1;
}
}
}
}
int main(){
cin>>n>>m;
cin>>a>>b;
for(int i=1;i<=a;i++){
int x,y;
cin>>x>>y;
vis[x][y]=1;
ans[x][y]=0;
node.x=x;
node.y=y;
q.push(node);
}
bfs();
for(int i=0;i<b;i++){
int s,d;
cin>>s>>d;
cout<<ans[s][d]<<endl;
}
return 0;
}
填涂颜色
- 在外围加一圈
- 从第一个点开始是0就走，否则不走
- 加入队列
- 统计答案
#include<bits/stdc++.h>
using namespace std;
int n;
int dx[5]={0,0,0,-1,1};
int dy[5]={0,-1,1,0,0};
int a[40][40],vis[31][31];
queue<pair<int,int> >q;
void bfs(int x,int y){
vis[x][y]=1;
q.push(make_pair(x,y));
while(q.size()){
int fx=q.front().first,fy=q.front().second;q.pop();
for(int i=1;i<=4;i++){
int nx=fx+dx[i];
int ny=fy+dy[i];
if(nx>=0&&ny>=0&&nx<=n+1&&ny<=n+1&&(!vis[nx][ny])){
vis[nx][ny]=1;
q.push(make_pair(nx,ny));
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==0){
vis[i][j]=0;
}
else{
vis[i][j]=2;
}
}
}
bfs(0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[i][j]==0){
cout<<2<<" ";
}
else{
cout<<a[i][j]<<" ";
}
}
cout<<'\n';
}
return 0;
}