WA16个点求调
查看原帖
WA16个点求调
699727
ChenYH_楼主2024/5/18 11:09

大概知道是每次主函数进dfs没初始化,但是memset会超时,这咋解决啊qwq

#include<bits/stdc++.h>
#define maxn 1075
using namespace std;

int H,W;	
char s[maxn][maxn];
int b[maxn][maxn];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int cnt,ans=1;

void dfs(int x, int y) {
	if (b[x][y]==1 || s[x][y]=='#' || x<1 || x>H || y<1 || y>W) return ;
	cnt++;
	b[x][y]=1;
	if (s[x][y]=='$') return ;
	for (int i=0; i<4; i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if (b[nx][ny]==1 || s[nx][ny]=='#') continue;
		if (nx<1 ||nx>H || ny<1 || ny>W) continue;
		dfs(nx,ny);
	}
}

int main () {
	cin>>H>>W;
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) {
			cin>>s[i][j];
		}
	}
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) {
			if (s[i][j]=='#') {
				for (int k=0; k<4; k++){
					int nx=i+dx[k],ny=j+dy[k];
					if (s[nx][ny]!='#' && nx>0 && ny>0 ) s[nx][ny]='$';
				}
			}
		}
	}
	for (int i=1; i<=H; i++) {
		for (int j=1; j<=W; j++) {
			if (s[i][j]=='#' || s[i][j]=='$') continue;
			cnt=0;
			//本来这一行memset 
			dfs(i,j);
			ans=max(ans,cnt);
		}
	}
	cout<<ans<<endl;
	return 0;
}
2024/5/18 11:09
加载中...