Acwing 1402. 星空之夜（搜索+哈希）

题目链接：点击这里

题目大意：
给定一个长为 n n n ，宽为 m m m 的 01 01 01 矩阵， 1 1 1 代表连通（连通形式为 8 8 8 连通），将每一个联通块标上相同的字母，形态相似（通过对称旋转可转换成同一种形式）的连通块字母也要相同，输出标记后的矩阵

题目分析：
求连通块可以使用 f l o o d   f i l l flood\ fill flood fill 的搜索方式进行搜索，此题的关键是如何通过哈希来判断连通块形态相似
给出一种哈希函数为：求连通块内所有点的两点距离之和
此哈希值是一个浮点数，但切记不可不开根号，因为距离平方和是一个大概率会冲突的哈希函数，而距离和冲突概率则会小很多
如果只使用此哈希还是出现了冲突则需要引入新的哈希来减小冲突（此题不需要）

具体细节见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
//#define int ll
using namespace std;
int read()
{
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 105;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct node{
	int x,y;
}nod[maxn*maxn];
int n,m,x,cnt,id='a';
char a[maxn][maxn];
void dfs(int x,int y)
{
	nod[++cnt].x = x;nod[cnt].y = y;
	a[x][y] = '0';
	for(int i = x-1;i <= x+1;i++)
	for(int j = y-1;j <= y+1;j++)
	{
		if(i==x && j==y) continue;
		if(a[i][j] == '1') dfs(i,j);
	}
} 
double get_hash()
{
	double res = 0;
	for(int i = 1;i <= cnt;i++)
		for(int j = i+1;j <= cnt;j++)
			res += sqrt((nod[i].x-nod[j].x)*(nod[i].x-nod[j].x)+(nod[i].y-nod[j].y)*(nod[i].y-nod[j].y));
	return res;
}
char get_id(double key)
{
	static double hash[30];
	static int id = 0;
	for(int i = 1;i <= id;i++) if(fabs(key-hash[i]) < eps) return i-1+'a';
	hash[++id] = key;
	return id-1+'a';
}
signed main()
{
	m = read(),n = read();
	for(int i = 1;i <= n;i++) scanf("%s",a[i]+1);
	for(int i = 1;i <= n;i++)
	for(int j = 1;j <= m;j++)
		if(a[i][j] == '1') 
		{
			cnt = 0,dfs(i,j);
			char ch = get_id(get_hash());
			for(int k = 1;k <= cnt;k++) a[nod[k].x][nod[k].y] = ch;
		}
	for(int i = 1;i <= n;i++) puts(a[i]+1); 
	return 0;
}