九十分蒟蒻求助!!!!!!!!!!#10WA了,开longlong也不行
查看原帖
九十分蒟蒻求助!!!!!!!!!!#10WA了,开longlong也不行
759274
Stevehim楼主2022/8/25 15:54
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#define maxn 1505
using namespace std;
typedef long long ll;
//bfs
char a[maxn][maxn];
int book[maxn][maxn] = {1}; //判定是否访问 
ll _max = 0; // 最大值 
ll n, m;
ll sum = 0; //单个星座星星 
ll sum_2 = 0; //单个星系星星 
int num_galaxy[maxn];
struct node{
	int x;
	int y;
};
queue<node>q;
int _next[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//存储偏移量
void bfs(int x, int y){
	int tx,ty,k;
	node z;
	q.push((node){x,y}); //强制输入
	book[x][y] = 1;
	while(!q.empty()){
		z = q.front();
		for(k = 0; k < 8; k++){
			tx = z.x + _next[k][0];
			ty = z.y + _next[k][1];
			if(tx < 1||tx > n|| ty < 1 || ty > m){ //超界限了 
				continue;
			}
			if(a[tx][ty] == '*' && book[tx][ty] == 0){ //达标且未访问 
				sum ++;
				if(sum > _max){
					_max = sum;
				}
				book[tx][ty] = 1;
				q.push((node){tx,ty}); //放入队列 
			}
		}
		q.pop();
	}
	return;
}
int ans = 0;
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		scanf("%s",a[i]+1);
	}
	for(int i = 1; i <= n+1; i++){ //初始化 
		for(int j = 1; j <= m+1; j++){
			book[i][j] = 1;
			if(a[i][j] == '*'){
				book[i][j] = 0;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] == '*'&& book[i][j] == 0){
				sum++;
				bfs(i,j);
				if(num_galaxy[sum]==0){
					ans++;
					num_galaxy[sum]++;
					sum_2 = sum * num_galaxy[sum]; //计算单个星系值 
					if(_max < sum_2){
						_max = sum_2;
					}
				}else{
					num_galaxy[sum]++;
					sum_2 = sum * num_galaxy[sum];
					if(_max < sum_2){
						_max = sum_2;
					}
				}
				sum = 0;
			}
		}
	}
	cout << ans << " " << _max;
    return 0;
}

2022/8/25 15:54
加载中...