#include<cstdio>
using namespace std;
char a[101][101];
int ans;
int n,m;
void dfs(int x,int y){
    a[x][y]='.';
    int dx,dy;
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            dx=x+i;
            dy=y+j;
            if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W'){
                dfs(dx,dy);
            }
        }
    }
    return;
} 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++){
    	scanf("%s",a[i]);//避免换行带来问题这里直接读入字符串
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]=='W'){//如果是W的话就直接开始遍历
                dfs(i,j);
                ans++;//水潭加一处
            }
        }
    }
    printf("%d",ans);
    return 0;
}

具体看 P1451求细胞数量 的我的题解,只需改一下就行了
最大不同就是一个4格检测,这个8格检测

#include<iostream>
#include<string>
using namespace std;
//8格了!!!
int x[8]={-1,1,0,0,1,-1,-1,1};
int y[8]={0,0,-1,1,1,-1,1,-1};
char a[1000][1000];//这次为二维字符数组
int us[1000][1000],n,m,ans=0;
void dfs(int q,int w)
{
 us[q][w]=1;
 for(int i=0;i<8;i++)//8格了!!!
 {
  //这次为"W"
  if(q+x[i]>=0 && q+x[i]<n && w+y[i]>=0 && w+y[i]<m && us[q+x[i]][w+y[i]]==0 && a[q+x[i]][w+y[i]]=='W')
  {
   dfs(q+x[i],w+y[i]);
  }
 }
}
int main()
{
 string s;
 cin>>n>>m;//输入
 for(int i=0;i<n;i++)
 {
  cin>>s;
  for(int j=0;j<m;j++)
  {
   us[i][j]=0;
   a[i][j]=s[j];
  }
 }
 for(int i=0;i<n;i++)
 {
  for(int j=0;j<m;j++)
  {
   if(us[i][j]==0 && a[i][j]=='W')//这次为"W"
   {
    ans++;
    dfs(i,j);
   }
  }
 }
 cout<<ans;//输出
 return 0;//完结散花
}

题意

输入一个 $n \times m$ 的田，里面有水坑（W）和旱地（.），找有多少个水坑

水坑定义：一个水坑的八方如果有水坑，那么算它们为一个水坑

思路

本题思路与 P1451. 求细胞数量 相似，只是方向从四面改成了八方，具体思路见 题解 - P1451. 求细胞数量

代码

#include <bits/stdc++.h>
using namespace std;
string s;
int cnt,n,m;
int x[8] = {-1,-1,-1,0,0,1,1,1},y[8] = {-1,0,1,-1,1,-1,0,1};	// 八个方向的方向数组
bool f[105][105],a[105][105];
void dfs(int z,int k){
//	printf("%d %d\n",i,j);
	f[z][k] = 1;	// 标记遍历过了
	for (int i = 0;i < 8;i++){
		// 如果第 i 个方向是水坑且没被遍历，就遍历这个水坑
		if (a[z + x[i]][k + y[i]] && !f[z + x[i]][k + y[i]])	dfs(z + x[i],k + y[i]);
	}
}
int main(int argc, char **argv){
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		cin >> s;
		for (int j = 1;s[j - 1];j++){
			if (s[j - 1] == 'W')	a[i][j] = 1;	// 如果是水坑
			else	a[i][j] = 0;	// 如果是旱地
		}
	}
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= m;j++){
			if (a[i][j] && !f[i][j]){	// 如果是水坑且没被遍历
				cnt++;
				dfs(i,j);
			}
		}
	}
	cout << cnt;
	return 0;
}

题意

计算连通分量

思路

也是相当esay啊，直接dfs搜索八联通，然后找一个消一个。

代码

#include<iostream>
#define N 200
#define M 200
using namespace std;
int n(0);
int m(0);
bool a[N][M]{};
int main(){
	void dfs(int,int);
	cin>>n>>m;
	for(int i(1);i<=n;i++)
		for(int j(1);j<=m;j++){
			char x(0);
			cin>>x;
			a[i][j]=x-'.';
		}
	int sum(0);
	for(int i(1);i<=n;i++)
		for(int j(1);j<=m;j++)
			if(a[i][j]){
				sum++;
				dfs(i,j);
			}
	cout<<sum;
	return 0;
}
void dfs(int x,int y){
	a[x][y]=false;
	int fx[8]{1,1,1,0,0,-1,-1,-1};
	int fy[8]{1,0,-1,1,-1,1,0,-1};
	for(int i(0);i<8;i++)
		if(a[x+fx[i]][y+fy[i]])
			dfs(x+fx[i],y+fy[i]);
}

广告

点我直通博客，超多精彩内容

#include #include #include using namespace std; vectorg[1001]; int vis[101][101]; int maxn=0; int n,m; char s[101][101]; int p=0;

void dfs(int k,int d){ s[k][d]='.'; if(d+1<=m){ if(s[k][d+1]!='.'){ dfs(k,d+1); } } if(k+1<=n){ if(s[k+1][d]!='.'){ dfs(k+1,d); } } if(d-1>0){ if(s[k][d-1]!='.'){ dfs(k,d-1); } } if(k-1>0){ if(s[k-1][d]!='.'){ dfs(k-1,d); } } if(d+1<=m&&k+1<=n){ if(s[k+1][d+1]!='.'){ dfs(k+1,d+1); } } if(d-1>0&&k+1<=n){ if(s[k+1][d-1]!='.'){ dfs(k+1,d-1); } } if(d+1<=m&&k-1>0){ if(s[k-1][d+1]!='.'){ dfs(k-1,d+1); } } if(d-1>0&&k-1>0){ if(s[k-1][d-1]!='.'){ dfs(k-1,d-1); } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>s[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j]!='.'){ dfs(i,j); p++; }
} } cout<<p; }