【暴力】[NOI Online #3 入门组]观星

$Link$Link

$luogu\ P6566$luogu P6566

$Description$Description

$Sample$Sample $Input$Input $1$1

5 7
*......
..**..*
.*...*.
...*...
....*..

$Sample$Sample $Output$Output $1$1

3 4

$Sample$Sample $Input$Input $2$2

10 10
**..**.**.
***....*..
*...**.**.
...*..*...
..........
**...**.*.
..*.*....*
..........
***..*.*..
.***..*...

$Sample$Sample $Output$Output $2$2

4 12

$Hint$Hint

$Train$Train $of$of $Thought$Thought

就直接暴力统计区块

$Code$Code

#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

int ans, n, m, tt, op, sum;
int b[1505][1505], a[1505][1505], t[3000005], ansx[3000005];
int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[8] = {1, -1, 1, -1, 0, 1, -1, 0}; 

bool cmp(int i, int j)
{return i > j;}

bool legal(int x, int y)
{
	if (x > n || x < 1 || y > m || y < 1) return 0;
	return 1;
}//判断是否超出边界

int work(int x, int y)
{
	ans++;
	b[x][y] = 1;
	for (int i = 0; i < 8; ++i)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (legal(xx, yy) && a[xx][yy] && !b[xx][yy]) 
		work(xx, yy);
	}
	return ans;
}

int main()
{
	char c;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
	 	c = getchar();
		for (int j = 1; j <= m; ++j)
		{
			c = getchar();
			if (c == '*') a[i][j] = 1;
			else b[i][j] = 1;
		}
	}
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		if (!b[i][j]) ans = 0, t[++tt] = work(i, j);//找出每一个星座
	sort(t + 1, t + tt + 1, cmp);
	for (int i = 1; i <= tt; ++i)
	{
		if (i == 1) sum = t[i];
 		else if (t[i] != t[i - 1]) ansx[++op] = sum, sum = t[i];
		else sum += t[i];
	}
	ansx[++op] = sum;
	sort(ansx + 1, ansx + op + 1);
	printf("%d %d", op, ansx[op]);
	return 0;
}