dfs,bfs都写了,WA 0分求助
查看原帖
dfs,bfs都写了,WA 0分求助
662953
_ZXWDS楼主2022/10/13 10:59

dfs:

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,f[10000000];
char a[2010][2010];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,-1,-1,-1,0,1,1,1};

int dfs(int x,int y){
	a[x][y] = '.';
	int ans=1;
	for(int i=0;i<8;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0 && xx<n && yy>=0 && yy<m && a[xx][yy]=='W'){
			ans++;
			a[xx][yy]='.';
			dfs(xx,yy);
		}
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(a[i][j]=='W'){
				int t = dfs(i,j);
				f[t]++;
			}
	int ans = 0;
	for(int i=1;i<=n*m;i++){
		if(f[i]!=0){
			sum++;
			ans = max(ans,i);
		}
	}
	cout<<sum<<" "<<ans;
	return 0;
}

bfs:

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,sum;
int f[100005],fl[100005];
bool vis[1510][1510];
char ch[1510][1510];
struct node{int x,y;};
queue<node> q;
int dx[8] = {-1,-1,-1,0,0,1,1,1},dy[8] = {-1,0,1,-1,1,-1,0,1};

void bfs(int x,int y){
	q.push((node){x,y});
	vis[x][y] = 1;
	while(!q.empty()){
		node xx = q.front();
		q.pop();
		for(int i=0;i<8;i++){
			node yy;
			yy.x = xx.x+dx[i];
			yy.y = xx.y+dy[i];
			if(yy.x<1 || yy.y<1 || yy.x>n || yy.y>n || ch[yy.x][yy.y]=='.' || vis[yy.x][yy.y]==1)
				continue;
			ans++;
			vis[yy.x][yy.y] = 1;
			 q.push(yy);
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%c",&ch[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(vis[i][j]==0 && ch[i][j]=='*'){
				ans = 1;
				bfs(i,j);
				f[ans]++;
			}
	int tmp=0;
	for(int i=0;i<=19999;i++){
		if(f[i]){
			sum++;
			tmp = max(tmp,i);
		}
	}
	printf("%d %d",sum,tmp);
	return 0;
} 

如果是代码语法问题请狠狠骂我qwq

2022/10/13 10:59
加载中...