我是蒟蒻,dfs半小时愣是调不出来,有愧祖宗
查看原帖
我是蒟蒻,dfs半小时愣是调不出来,有愧祖宗
1357615
liujunyua楼主2024/10/19 10:57
#include<iostream>
#include<cstdio>
using namespace std;

const int N=101;
const int d[][2]={{0,0},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};

int n,m;
char a[N][N];
int ans;


void dfs(int x,int y){
	if(a[x][y]=='.')
	  return ;
	for(int i=1;i<=8;i++){
		int xx=x+d[i][0];
		int yy=y+d[i][1];
		if(xx<1||yy<1||xx>n||yy>m)
		  continue ;
		if(a[xx][yy]=='W'){
			a[xx][yy]='.';
			dfs(xx,yy);
		}
	}
}


int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	scanf("%d%d",&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(a[i][j]=='W'){
	  	    	a[i][j]='.';
	  	  	    dfs(i,j);
	  	  	    ans++;
		  }
	  }
	  printf("%d",ans);
}

蒟蒻求调

2024/10/19 10:57
加载中...