深度优先搜索

深度优先搜索的本质是以一种有规律的形式去遍历所有的可能情况。

全排列问题

背景：3个同学来排队，有哪几种排队方法

1.For循环暴力枚举

int vis[4]={0};
for(int i=1;i<=3;i++){
    vis[i]=1;
    for(int j=1;j<=3;j++){
        if(vis[j]) continue;
        vis[j]=1;
        for(int x=1;x<=3;x++){
            if(vis[x]) continue;
            cout<<i<<" "<<j<<" "<<x<<"\n";
        }
        vis[j]=0;
    }
    vis[i]=0;
}

其中使用了vis数组，进行了回溯操作。如果同学的个数逐渐增多，

我们很难再使用for循环，可以使用递归的方式来解决问题。这种递归+回溯的遍历方式就是搜索。

2.搜索暴力枚举

int vis[4];
int a[4];
void dfs(int x){
    if(x==4){
        cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<"\n";
        return;
    }
    for(int i=1;i<=3;i++){
        if(vis[i]) continue;
        vis[i]=1;
        a[x]=i;
        dfs(x+1);
        vis[i]=0;
    }
}

像刚刚这种，一条线走到底的方式，我们叫做深度优先搜索，每次都会把选定的某条路走完再走下一条路。

连通块问题

背景：有一张3*3的地图，其中-表示平地，#表示山，山有可能是连绵的。

如何找到所有的山?

我们可以使用搜索把一片山全都标记了，搜索了几次，就是有多少山。

int fx[4][2]={0,1,1,0,0,-1,-1,0};
int vis[100][100];
void dfs(int x,int y){
   	vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=fx[i][0]+x;
        int yy=fx[i][1]+x;
        if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||mp[xx][yy]=='-') continue;
        dfs(xx,yy);
    }
}
int main(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i][j]&&mp[i][j]=='-'){
                ans++;
                dfs(i,j);
            }
        }
    }
}

涂色部分代码

#include<bits/stdc++.h>
using namespace std;
int fx[4][2]={0,1,1,0,0,-1,-1,0};
int n,m;
int mp[200][200];
int vis[200][200];
void dfs(int x,int y){
	for(int i=0;i<4;i++){//四个方向 
		int xx=x+fx[i][0];
		int yy=y+fx[i][1];
		 if(xx<1||xx>n||yy<1||yy>n){//越界 
		 	continue; 
		 }
		 if(mp[xx][yy]==1){
		 	continue;
		 }
		 if(vis[xx][yy]==1){
		 	continue;
		 }
		 vis[xx][yy]=1;
		 dfs(xx,yy);
	}
}
int main(){
	
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>mp[i][j];
	}
	for(int j=1;j<=n;j++){//处理第一行 
		if(mp[1][j]==0&&!vis[1][j]){
		
		}
	}
	for(int j=1;j<=n;j++){//处理最后一行 
		if(mp[n][j]==0&&!vis[n][j]){
			
		}
	}
	
	for(int i=1;i<=n;i++){//处理左列 
		if(mp[i][1]==0&&!vis[i][1]){
		
		}
	}
	for(int i=1;i<=n;i++){//处理右列 
		if(mp[i][n]==0&&!vis[i][n]){
			
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(？) cout<<2<<" ";
			else cout<<mp[i][j]<<" ";
		}
		cout<<"\n";
	} 
	
}

枚举所有情况

int n,ans=10000000;
void dfs(int x,int v){
	if(x==n+1){
		ans=min(ans,v);
		return;
	} 
	if(v>=a[x]){
		dfs(x+1,v-a[x]);
	}
	dfs(x+1,v);
}
int main(){
	int v;cin>>v;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1,v);
}