本期主要讲解进阶 \(\text{DFS}\)。
知识点
\(\text{DFS}\) 求解连通块问题：
-
定义：若一个点集中的所有点都能互达，且与集合外的点无法互达，则称此点集为一个连通块。
-
考查方式：求连通块数量 / 大小 / 周长。
例题
T1
在 \(\text{DFS}\) 函数中传入参数 \(x\) 和 \(str\)，分别表示当前字符串的长度和当前字符串。
每次搜索都遍历所有可用字符串，不断尝试进行拼接，若新增长度 \(>0\) 且字符串使用次数 \(<2\)，则继续进行下一层搜索。
#include<bits/stdc++.h>
using namespace std;
int n,ans=-1e9;
string str[31];
int vis[31];
string ch;
int match(string a,string b){
if(a.size()==1){
if(a[0]==b[0]) return b.size();
return 0;
}
for(int i=1;i<min(a.size(),b.size());i++){
string t1=a.substr(a.size()-i),t2=b.substr(0,i);
if(t1==t2) return b.size()-i;
}
return 0;
}
void dfs(int x,string s){
ans=max(ans,x);
for(int i=1;i<=n;i++){
int len=match(s,str[i]);
if(len>0&&vis[i]<2){
vis[i]++;
dfs(x+len,str[i]);
vis[i]--;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>str[i];
cin>>ch;
dfs(0,ch);
cout<<ans;
return 0;
}
T2
初始坐标为 \((0,0)\)，若扩展后坐标合法，则不断 \(\text{DFS}\) 向右进行扩展，当到达 \((m,n)\) 时就将方案数 \(ans \gets ans+1\) 即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,total;
int dx[]={1,1,2,2},dy[]={2,-2,1,-1};
void dfs(int x,int y){
if(x==m&&y==n){
total++; return;
}
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0&&xx<=m&&yy>=0&&yy<=n) dfs(xx,yy);
}
}
int main(){
cin>>n>>m;
dfs(0,0);
cout<<total;
return 0;
}
习题
T3
求连通块数量的典题。
遍历整个矩阵，若当前点 \(a_{i,j} \neq 0\) 且未被访问，则从此处开始 \(\text{DFS}\)。
在搜索过程中，我们先将连通块总数 \(sum \gets sum+1\)，然后不断尝试从当前点出发向四个方向扩展，若有一个方向的点也 \(\neq 0\)，则标记此点并继续搜索。
若当前点是不合法的，说明连通块遍历完成，直接结束搜索。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,cell[131][131],dx[]={-1,0,1,0},dy[]={0,-1,0,1};
void dfs(int x,int y){
if(x>n||y>m||x<0||y<0) return;
cell[x][y]=0;
for(int i=0;i<4;i++)
if(cell[x+dx[i]][y+dy[i]])
dfs(x+dx[i],y+dy[i]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%1d",&cell[i][j]);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(cell[i][j]) ans++,dfs(i,j);
}
}
printf("%d",ans);
return 0;
}
T4
直接找到起始点开始搜索，期间不断向安全地扩展即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,sum;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
char mp[31][31];
bool vis[31][31];
void dfs(int x,int y){
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(vis[xx][yy]==0&&mp[xx][yy]=='.'&&xx>=1&&xx<=n&&yy>=1&&yy<=m){
vis[xx][yy]=1,sum++;
dfs(xx,yy);
//vis[xx][yy]=0,sum--;
}
}
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='@') sx=i,sy=j;
}
vis[sx][sy]=1,sum++;
dfs(sx,sy);
cout<<sum;
return 0;
}
T5
读到一个 # 就开始搜索。
面积很好求，就是和 T3 一样求连通块个数。
周长就是如果当前点旁边若有一个点为 .，就令周长 \(c \gets c+1\)。
求出一个连通块后，根据题目规则更新全局最优答案即可。
#include<bits/stdc++.h>
using namespace std;
int n;
char ice[1031][1031];
int S,C,s,c;
bool vis[1031][1031];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void update(){
if(s>S) S=s,C=c;
if(s==S&&c<C) C=c;
}
void dfs(int x,int y){
if(vis[x][y]) return;
vis[x][y]=1,s++;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>n||ice[xx][yy]=='.') c++;
if(ice[xx][yy]=='#') dfs(xx,yy);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>ice[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ice[i][j]=='#'&&!vis[i][j]){
s=c=0;
dfs(i,j);
update();
}
}
}
cout<<S<<' '<<C;
return 0;
}