BFS+桶排 90WA求助
查看原帖
BFS+桶排 90WA求助
120438
Lacrymabre楼主2020/5/29 21:46

WA了最后一个点求大佬帮助

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<set>

#define ll long long
#define db double
#define MAX 0x7fffffff
#define init inline int
#define INF 0X3fffffff

using namespace std;

ll tox[9]={0,1,0,-1,0,1,1,-1,-1};
ll toy[9]={0,0,1,0,-1,-1,1,1,-1};
ll n,m,s,que[15500][55];
char a[2001][2001];
ll res,ans;
ll ma[1000001];

void bfs(ll x,ll y)
{
	res=1;
	ll head=1,tail=1;
	ll i=1;
	que[tail][1]=x; 
	que[tail][2]=y;
	a[x][y]='.';
	tail++; 
	while(head<tail) 
	{
		int qx=que[head][1];
		int qy=que[head][2];
		for(i=1;i<=8;i++) 
		{
			int x1=qx+tox[i];
			int y1=qy+toy[i];
			if(x1>0 && x1<=n && y1>0 && y1<=m && a[x1][y1]=='*')
			{
				a[x1][y1]='.';
				que[tail][1]=x1;
				que[tail][2]=y1;
				tail++;
				res++;
			}
		}
		head++;
	}
	if(!ma[res]) ma[res]=1;
	else ma[res]++;
} 

int main()
{
	ll i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[i][j]=='*')
			{
				bfs(i,j);
			}
		}
	}
	
	for(int i=0;i<=100000;i++) {
		if(ma[i]) s++;
		res=i*ma[i];
		if(res>ans) ans=res;
	}
	cout<<s<<" "<<ans;
//	fclose(stdin);fclose(stdout);
	return 0;
}

2020/5/29 21:46
加载中...