算法:FloodFill + 哈希
时间复杂度:$O(m \times n)$
$FloodFill$ 算法,即洪水灌溉算法,应该十分简单,不在此详述。
难点在于如何判断两个形状即星群是否相同(不管朝向),此时就需要用到哈希,用欧几里得距离判断形状即星群是否相同,再用对应的字母去覆盖原先的地图即可。
第一次比较难想。
欧几里得距离:一个连通块两两点之间的距离的和。
浮点数判断记得加一个 $eps$,以防止精度问题。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef pair<int , int> PII;
const int N = 110;
const double eps = 1e-6;
int n, m, top = 0;
bool st[N][N];
string g[N];
PII q[N * N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
double get_dist(PII a, PII b)
{
double dx = a.x - b.x;
double 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_dist(q[i], q[j]);
}
}
return sum;
}
char get_id(double x)
{
static double hash[30];
static int id = 0;
for (int i = 0; i < id; ++i) {
if (fabs(hash[i] - x) < eps) {
return i + 'a';
}
}
hash[id++] = x;
return id + 'a' - 1;
}
void dfs(int xs, int ys)
{
for (int i = 0; i < 8; ++i) {
int x = xs + dx[i], y = ys + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1' && !st[x][y]) {
st[x][y] = true;
q[top++] = {x, y};
dfs(x, y);
}
}
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; ++i) cin >> g[i];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (g[i][j] == '1') {
top = 0;
memset(st, false, sizeof(st));
q[top++] = {i, j}, st[i][j] = true;
dfs(i, j);
char c = get_id(get_hash());
for (int k = 0; k < top; ++k) {
g[q[k].x][q[k].y] = c;
}
}
}
}
for (int i = 0; i < n; ++i) cout << g[i] << endl;
return 0;
}