思路:
#include <iostream>
using namespace std;
int sum=0;//用sum记录
//上下左右用x,y数组、
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
//周围八个点用
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
//dfs每一个符合条件的点
//从每一个符合条件的点去深搜,染整个连通块
void dfs(int i,int j);
int main() {
//输入
//遍历
for()
for()
if(满足条件){
dfs(); //用dfs染色,遍历把一个整体
sum++
}
//输出
return 0;
}
void dfs(int a,int b){
//当遍历到四周边界 或 到了不满足条件的点
if( 边界 || 不满足条件)
return ;
//对 (a,b)点 进行染色
ans[a][b]=不满足的条件
//递归周围的点
for(int i=0;i<4;i++)
dfs(a+x[i],b+y[i]);
}
增强:需要经过遍历处理数据。
例题:
P1451 求细胞数量 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1451
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
int ans[110][110];
void dfs(int a,int b);
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%1d",&ans[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ans[i][j]!=0){
dfs(i,j);
sum++;
}
}
cout<<sum<<endl;
return 0;
}
void dfs(int a,int b){
if(a<1 || b <1 || b>m || a>n || ans[a][b]==0)
return ;
ans[a][b]=0;
for(int i=0;i<4;i++)
dfs(a+x[i],b+y[i]);
}
P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1596
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
char ch;
int ans[110][110];
void dfs(int a,int b);
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='W')
ans[i][j]=1;
if(ch=='.')
ans[i][j]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ans[i][j]==1){
dfs(i,j);
sum++;
}
cout<<sum<<endl;
return 0;
}
void dfs(int a,int b){
if(a<1 || b <1 || b>m || a>n || ans[a][b]==0)
return ;
ans[a][b]=0;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
dfs(a+i,b+j);
}
增强:需要经过遍历处理数据。 P1506 拯救oibh总部 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1506
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
char ch;
int ans[510][510];
int x[4]={0,0,-1,1};
int y[4]={1,-1,0,0};
void dfs(int a,int b);
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='0')
ans[i][j]=1;
if(ch=='*')
ans[i][j]=0;
}
for(int i=1;i<=n;i++){
if(ans[i][1]==1)
dfs(i,1);
if(ans[i][m]==1)
dfs(i,m);
}
for(int i=1;i<=m;i++){
if(ans[1][i]==1)
dfs(1,i);
if(ans[n][i]==1)
dfs(n,i);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ans[i][j]==1)
sum++;
}
cout<<sum<<endl;
return 0;
}
void dfs(int a,int b){
if(a<1 || b <1 || b>m || a>n || ans[a][b]==0)
return ;
ans[a][b]=0;
for(int i=0;i<=3;i++)
dfs(a+x[i],b+y[i]);
}
P4961 小埋与扫雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P4961
#include<bits/stdc++.h>
#define DB cout<<"............................"<<endl
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define pi acos(-1,0)
#define ms(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const double E=exp(1);
using namespace std;
int n,m,sum=0;
int ans[1010][1010];
void dfs(int i,int j);
int main(){
IOS;
ms(ans,-1);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>ans[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ans[i][j]==1)
for(int k=-1;k<=1;k++)
for(int _=-1;_<=1;_++)
if(ans[i+k][j+_]==0)
ans[i+k][j+_]=2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ans[i][j]==2){
int temp=0;
for(int k=-1;k<=1;k++)
for(int _=-1;_<=1;_++)
if(ans[i+k][j+_]!=0)
temp++;
if(temp==9)
sum++;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ans[i][j]==0){
dfs(i,j);
sum++;
}
}
cout<<sum<<endl;
return 0;
}
void dfs(int a,int b){
//if(ans[i][j]!=0) return ;
ans[a][b]=2;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++){
if(ans[a+i][b+j]==0)
dfs(a+i,b+j);
}
}
P1331 海战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1331
#include<bits/stdc++.h>
using namespace std;
char a[1010][1010];
bool is(int i,int j);
int p[1010][1010]={0};
int total=0;
int n,m;
void dfs(int a,int b);
int x[4]={1,0,0,-1};
int y[4]={0,-1,1,0};
int main(){
ios::sync_with_stdio(0);
cout.tie(0);cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(is(i,j)){
cout<<"Bad placement."<<endl;
return 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]=='#' and p[i][j]==0){
dfs(i,j);
total++;
}
}
cout<<"There are "<<total<<" ships."<<endl;
return 0;
}
void dfs(int i,int j){
if(i>0 and j>0 and i<=n and j<=m){
p[i][j]=1;
for(int k=0;k<4;k++){
i+=y[k],j+=x[k];
if(a[i][j]=='#' and p[i][j]==0)
dfs(i,j);
i-=y[k],j-=x[k];
}
}
}
bool is(int i,int j){
int s=0;
if(a[i][j]=='#') s++;
if(a[i+1][j]=='#') s++;
if(a[i][j+1]=='#') s++;
if(a[i+1][j+1]=='#') s++;
if(s==3) return 1;
return 0;
}
|