【AcWing】蓝桥杯集训每日一题Day16|哈希|FloodFill算法|字典序最小|映射|1402.星空之夜(C++)

1402.星空之夜

1402. 星空之夜 - AcWing题库
难度：中等
时/空限制：1s / 64MB
总通过数：3415
总尝试数：7434
来源： usaco training 5.1
算法标签 Flood Fill哈希DFSBFS

题目内容

夜空深处，闪亮的星星以星群的形式出现在人们眼中，形态万千。
一个星群是指一组非空的在水平，垂直或对角线方向相邻的星星的集合。
一个星群不能是一个更大星群的一部分。
星群可能是相似的。
如果两个星群的形状、包含星星的数目相同，那么无论它们的朝向如何，都认为它们是相似的。
通常星群可能有 8 种朝向，如下图所示：

现在，我们用一个二维 01 矩阵来表示夜空，如果一个位置上的数字是 1，那么说明这个位置上有一个星星，否则这个位置上的数字应该是 0。
给定一个夜空二维矩阵，请你将其中的所有星群用小写字母进行标记，标记时相似星群用同一字母，不相似星群用不同字母。
标注星群就是指将星群中所有的 1 替换为小写字母。

输入格式

第一行包含一个整数 W，表示矩阵宽度。
第二行包含一个整数 H，表示矩阵高度。
接下来 H 行，每行包含一个长度为 W 的 01 序列，用来描述整个夜空矩阵。

输出格式

输出标记完所有星群后的二维矩阵。
用小写字母标记星群的方法很多，我们将整个输出读取为一个字符串，能够使得这个字符串字典序最小的标记方式，就是我们想要的标记方式。
输出这个标记方式标出的最终二维矩阵。

数据范围

0≤W,H≤100,
0≤ 星群数量 ≤500,
0≤ 不相似星群数量 ≤26,
1≤ 星群中星星的数量 ≤160

输入样例：

23
15
10001000000000010000000
01111100011111000101101
01000000010001000111111
00000000010101000101111
00000111010001000000000
00001001011111000000000
10000001000000000000000
00101000000111110010000
00001000000100010011111
00000001110101010100010
00000100110100010000000
00010001110111110000000
00100001110000000100000
00001000100001000100101
00000001110001000111000

输出样例：

a000a0000000000b0000000
0aaaaa000ccccc000d0dd0d
0a0000000c000c000dddddd
000000000c0b0c000d0dddd
00000eee0c000c000000000
0000e00e0ccccc000000000
b000000e000000000000000
00b0f000000ccccc00a0000
0000f000000c000c00aaaaa
0000000ddd0c0b0c0a000a0
00000b00dd0c000c0000000
000g000ddd0ccccc0000000
00g0000ddd0000000e00000
0000b000d0000f000e00e0b
0000000ddd000f000eee000

样例解释

样例对应的星空图如下：

答案对应的标记后星空图如下：

题目解析

给一个矩阵，表示夜空，用黑色的块表示星星，连通块是八连通，只要有公共的边和点，都算连通
每一个连通块都算一个星群，星群里面有八种朝向，通过旋转和对称得到的这八种朝向是等价的
矩阵的形式是01二维矩阵，0表示空，1表示有星星
找出其中所有相同的星群，要把所有的星群归类，相同的归为一类，不同的归为另外一类
同一类星群用同一个小写英文字母标记，不同的星群用不同的英文小写字母标记

矩阵最大的长宽是100x100
星群数量最大是500
不相同的星群数量不会超过26个，一定可以用26个英文字母全部标记出来
标记的时候，是把星群用对应的字母替换掉，同一种星群用同一个字母替换
输出的时候，标记的方案有很多种，为了方便评测，规定输出一个字典序最小的方案，就是把每一行拼接起来，拼成一个字符串

1. 怎么去找一个星群

找一个星群就是找连通块，可以用Flood Fill算法，BFS、DFS或并查集，把所有连通块找出来

2. 如何区分星群

因为数据范围比较小，最多只会包含500个星群，每个星群中最多只会包含160个星星
可以使用暴力的方式去找，可以把星群所有出现的坐标存到一个数组里，每一次拿到一个新的星群之后，判断一下它在存过的星群里面有没有出现过，一个一个去比一遍，出现过的话，就是同一类，没有出现过的话，就是一种全新的类，时间复杂度是 $O (500 * 26 * 160)$ ，真实情况会比这个小很多
用暴力的方法比较，把八种朝向都枚举一遍，x8，最多1664万的计算量，可以过

[!NOTE] 如何优化
字符串哈希
因为只需要辨别是相同还是不同
把很多星群的所有信息，想办法把每一个星群，把它映射到一个数，再去判断这个数在前面有没有出现过

如何把星群转化成数
和字符串哈希一样，字符串哈希是把字符串转化成一个数，不能保证不冲突，有可能把不同形状的星群映射到同一个数，可以选择一种出现这种情况概率极低的一种哈希方式
这类算法不能保证一定是正确的，但是可以保证99%是正确的，不是精确算法，但是可以认为基本上是精确的
如字符串哈希，哈希值不一样，原字符串一定一样，哈希值一样，原字符串不一定一样，但是大概率是一样的
包括快排和哈希表

快排在平均意义上是nlogn，极限情况下时间复杂度是n^2，但是可以认为极限情况很难出现，
哈希表均摊是O(1)的，极端情况下也可以产生O(n)

怎么哈希
这个哈希方法应该尽量让它对旋转和对称是不敏感的，就是不管是旋转还是对称都不影响哈希值，
计算星群当中两个点两两之间，比如总共有k个点，就有 $C_{k}^2$ 种关系，每两个点之间的欧几里得距离，直线距离的总和
这种哈希方式是比较好的，如果是曼哈顿距离的话，冲突的概率更大

如果这种哈希方法答案错误的话，可以提供两个哈希值，哈希值1，就是计算一下直线距离的总和，再用另外一个哈希函数，两个哈希函数都判错的情况就比较低了

通过这样的哈希方式可以将星群映射成一个浮点数，还会去除掉旋转和对称的影响

整个图做一遍，包含1万个点，计算量是1万；星群最多是500个，每个星群枚举一遍，比较26次，是两万多的计算量

3. 如何保证字典序最小

对于大部分问题，要求字典序最小都不会增加题目的难度，主要是为了方便评测
从第一行开始枚举，当找到第一个1的时候，就把第一个1所在的连通块找出来，给这个连通块赋一个什么字母
出现过的话，赋出现过的字母
没有出现过的话，赋当前没有出现过的最小的字母
当前没有出现过的字母如果是a的话，是按照字符串的顺序一个一个枚举的，当前字母选a的话，一定比选大于a的字母的字典序更小
所以从前往后找的时候，如果发现了一个新的星群，就从小到大赋字母，这样可以保证字典序是最小的

比较浮点数是不是相等的时候，需要考虑精度(参考上一篇)

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110, M = 170;
const double eps = 1e-8;

int n, m;
char g[N][N];
PII q[M];    //用pair数组存所有的星群的坐标
int top = 0; //当前星群星星的数量
double hash_val[30]; //把前面所有出现过的星群的哈希值都存下来
int cnt = 0;  //当前不同星群的数量

void dfs(int a, int b)
{
	//先把当前的星星存下来
	q[top ++] = {a, b};
	//已经搜过的话，标记为0
	g[a][b] = '0';

	//枚举一下周围八个方向
	for (int x = a - 1; x <= a + 1; x ++)
		for (int y = b - 1; y <= b + 1; y ++)
			//如果发现当前的下标没有越界，并且当前的位置是1
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1')
				dfs(x, y);
}

double get_dist(PII& a, PII& b)
{
	//先求一下坐标之差
	double dx = a.x - b.x, dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

double get_hash()
{
	double sum = 0;
	//等于所有点对之间的距离之和
	for (int i = 0; i < top; i ++)
		for (int j = 0; j < i; j ++)
			sum += get_dist(q[i], q[j]);
	return sum;
}

char get_id()
{
	//先求当前星群的哈希值
	double val = get_hash();
	//判断之前有没有出现过
	for (int i = 0; i < cnt; i ++)
		if (abs(hash_val[i] - val) < eps)
			return 'a' + i;
	//如果没有出现过，存下来
	hash_val[cnt ++] = val;
	return 'a' + cnt - 1;
}

int main()
{
	//读入m和n
	scanf("%d%d", &m, &n);
	//读入整个矩阵
	for (int i = 0; i < n; i ++) scanf("%s", g[i]);

	//从前往后依次枚举每一个位置
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < m; j ++)
			//如果发现当前的位置是1的话，表示发现了一个新的星群
			if (g[i][j] == '1')
			{
				top = 0;  //先把top清空
				dfs(i, j); //floodfill 把所有和i，j连通的星星找出来
				//求一下当前星群的id
				char id = get_id();

				//把所有的格子赋成id
				for (int k = 0; k < top; k ++)
					g[q[k].x][q[k].y] = id;
			}
	//输出整个矩阵
	for (int i = 0; i < n; i ++) puts(g[i]);
	//puts等价于printf %s\n
}