Flood Fill + 哈希 - 星空之夜 - AcWing 1402
Flood Fill + 哈希 - 星空之夜 - AcWing 1402
一个星群是指一组非空的在水平,垂直或对角线方向相邻的星星的集合。
一个星群不能是一个更大星群的一部分。
星群可能是相似的。
如果两个星群的形状、包含星星的数目相同,那么无论它们的朝向如何,都认为它们是相似的。
通常星群可能有 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
分析:
① : 从 前 到 后 , 从 上 到 下 , 将 图 中 每 一 个 连 通 块 抠 出 来 。 ①:从前到后,从上到下,将图中每一个连通块抠出来。 ①:从前到后,从上到下,将图中每一个连通块抠出来。
② : 将 这 个 连 通 块 保 存 下 来 , 以 备 后 续 查 询 。 如 果 该 连 通 块 出 现 过 , 则 将 该 连 通 块 替 换 成 对 应 的 字 符 ; 否 则 按 顺 序 给 一 个 新 的 字 符 。 ②:将这个连通块保存下来,以备后续查询。\\\qquad如果该连通块出现过,则将该连通块替换成对应的字符;否则按顺序给一个新的字符。 ②:将这个连通块保存下来,以备后续查询。如果该连通块出现过,则将该连通块替换成对应的字符;否则按顺序给一个新的字符。
对 于 问 题 ① , 采 用 F l o o d F i l l 算 法 , 直 接 搜 索 。 对于问题①,采用Flood\ Fill 算法,直接搜索。 对于问题①,采用Flood Fill算法,直接搜索。
对 于 问 题 ② , 可 以 给 每 一 个 连 通 块 一 个 哈 希 值 , 接 下 来 考 虑 哈 希 函 数 : 对于问题②,可以给每一个连通块一个哈希值,接下来考虑哈希函数: 对于问题②,可以给每一个连通块一个哈希值,接下来考虑哈希函数:
哈 希 函 数 应 满 足 : Ⅰ 、 与 连 通 块 的 形 状 有 关 , 与 方 向 和 位 置 无 关 。 Ⅱ 、 避 免 冲 突 , 若 冲 突 , 则 增 加 哈 希 函 数 。 \qquad 哈希函数应满足:\\\qquadⅠ、与连通块的形状有关,与方向和位置无关。\\\qquadⅡ、 避免冲突,若冲突,则增加哈希函数。 哈希函数应满足:Ⅰ、与连通块的形状有关,与方向和位置无关。Ⅱ、避免冲突,若冲突,则增加哈希函数。
哈 希 函 数 : 考 虑 顺 序 地 计 算 连 通 块 内 各 点 之 间 的 距 离 ( 欧 几 里 得 距 离 ) 之 和 。 即 : \qquad 哈希函数:考虑顺序地计算连通块内各点之间的距离(欧几里得距离)之和。即: 哈希函数:考虑顺序地计算连通块内各点之间的距离(欧几里得距离)之和。即:
h a s h = ∑ i , j 且 i ≠ j d i s t a n c e ( v i , v j ) = ∑ i , j 且 i ≠ j ( x v i − x v j ) 2 + ( y v i − y v j ) 2 hash=\sum_{i,j且i≠j}distance(v_i,v_j)=\sum_{i,j且i≠j}\sqrt{(x_{v_i}-x_{v_j})^2+(y_{v_i}-y_{v_j})^2} hash=i,j且i=j∑distance(vi,vj)=i,j且i=j∑(xvi−xvj)2+(yvi−yvj)2
具体落实:
① 、 从 前 到 后 遍 历 连 通 块 , 每 次 把 连 通 块 内 所 有 点 的 坐 标 保 存 下 来 。 ①、从前到后遍历连通块,每次把连通块内所有点的坐标保存下来。 ①、从前到后遍历连通块,每次把连通块内所有点的坐标保存下来。
② 、 计 算 当 前 连 通 块 的 哈 希 值 , 并 查 表 比 对 。 若 存 在 该 哈 希 值 , 则 将 该 连 通 块 改 为 指 定 符 号 ; 若 不 存 在 , 按 顺 序 将 该 连 通 块 改 为 下 一 个 字 母 , 同 时 在 表 中 记 录 该 字 母 的 哈 希 值 。 ②、计算当前连通块的哈希值,并查表比对。\\\ \\ \qquad若存在该哈希值,则将该连通块改为指定符号;\\ \ \\\qquad若不存在,按顺序将该连通块改为下一个字母,同时在表中记录该字母的哈希值。 ②、计算当前连通块的哈希值,并查表比对。 若存在该哈希值,则将该连通块改为指定符号; 若不存在,按顺序将该连通块改为下一个字母,同时在表中记录该字母的哈希值。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define P pair<int,int>
#define x first
#define y second
using namespace std;
const int N = 110;
const double eps = 1e-6;
int n, m;
char s[N][N];
bool st[N][N];
char flag = 'a';
double H[30];
int d;
P q[N*2];
int top;
double get_dis(P a, P 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=i+1;j<top;j++)
sum += get_dis(q[i], q[j]);
return sum;
}
void turn(int k)
{
for(int i=0;i<top;i++)
{
int x = q[i].x, y = q[i].y;
s[x][y] = flag + k;
}
}
void dfs(int x, int y)
{
q[top ++] = {x, y};
st[x][y] = true;
for(int i=x-1;i<=x+1;i++)
for(int j=y-1;j<=y+1;j++)
if(i>0 && i<=n && j>0 && j<=m && s[i][j] == '1' && !st[i][j])
dfs(i, j);
}
void solve()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!st[i][j] && s[i][j] == '1')
{
top = 0;
dfs(i, j);
double hash = get_hash();
bool exist = false;
for(int i=0;i<d;i++)
if(fabs(hash - H[i]) < eps)
{
turn(i);
exist = true;
break;
}
if(!exist)
{
turn(d);
H[d] = hash;
++ d;
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
solve();
for(int i=1;i<=n;i++) printf("%s\n",s[i]+1);
return 0;
}