浅谈洪泛及思想
一、洪范概念
部分题目中，需要对一个连通区域的所有位置进行搜索，此时搜索没有明确的终点，直到将所有点都搜索到，这类问题，称为“洪泛”。
二、应用
例题大意：在10 10的二维数组中，有“ ”围住了15个“0”。若“0”在 号所围成的闭合曲线中水平线和垂直线交点的上，则“0”被围住。 现在以“1”替换“ ”，请你编程计算被“1”围住的0的个数。
#include<iostream>
using namespace std;
int n,m,cnt;
int vis[15][15];
int map[15][15];
int dir[5][2]={{0},{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y){
vis[x][y]=true;//状态不要恢复
for(int i=1;i<=4;i++){
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx>=0&&dy>=0&&dx<=11&&dy<=11&&!vis[dx][dy]&&map[dx][dy]!=1){
dfs(dx,dy);
}
}
}
int main(){
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
cin>>map[i][j];
dfs(0,0);
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
if(!vis[i][j]&&map[i][j]==0)
cnt++;
}
}
cout<<cnt;
return 0;
}三、复杂dfs
例题大意：给定一个N*M的由非负整数组成的矩阵，需要你取出其中的若干个数字，保证取出的任意两个数字不相邻（九宫格中间的数字与边缘的八个数字都算相邻），求出取出数字最大和是多少。
#include<iostream>
#include<cstring>
using namespace std;
int t,n,m,ans;
int map[10][10];
bool vis[10][10];
int dir[9][2]={{0},{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
bool Check(int x,int y){
for(int i=1;i<=8;i++){
int dx=x+dir[i][0],dy=y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&& vis[dx][dy])
return false;
}
return true;
}
void dfs(int x,int y,int sum){
if(x>n){
ans=max(ans,sum);
return ;
}
//逐行去判断，每行行内逐列去判断
//1. 当前元素不选
if(y<m)//该行内未判断完，继续判断同一行下一列
dfs(x,y+1,sum);
else//该行内判断完，从下一行第一列开始判断
dfs(x+1,1,sum);
//2. 当前元素考虑选
if(Check(x,y)){//判断是否能选
vis[x][y]=true;
if(y<m)
dfs(x,y+1,sum+map[x][y]);
else
dfs(x+1,1,sum+map[x][y]);
vis[x][y]=false;
}
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
memset(vis,0,sizeof(vis));
ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>map[i][j];
}
dfs(1,1,0);
cout<<ans<<endl;
}
return 0;
}四、学习感想
在学习洪泛的过程，写题就是刚。所以，大胆写，大胆思考，就行了。主要就是dfs。