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;
}