DFS + 计算连通分量的Hash值
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define EPS 1E-6 // 10的负6次方 == 0.000001
using P = pair<int, int>;
static constexpr int dirs[][2] {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, // 8连通的
{0, 1}, {1, 1}, {1, 0}, {1, -1}};
const int N = 110;
char g[N][N];
int n, m;
// 计算两点之间的欧几里德距离(是斜边不是曼哈顿距离)
double distance(P& a, P& b) {
const int dx = a.first - b.first;
const int dy = a.second - b.second;
return sqrt(dx * dx + dy * dy);
}
// 计算一个连通分量的Hash(哈希值)
double get_hash(vector<P>& component) {
const int n = component.size();
double ans = 0.0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans += distance(component[i], component[j]);
return ans;
}
double hashs[30];
int ids = 0;
// 获取连通分量的ID
char get_componentID(vector<P>& component) {
double hash = get_hash(component);
for (int i = 0; i < ids; ++i)
if (fabs(hashs[i] - hash) < EPS)
return i + 'a';
hashs[ids++] = hash;
return ids - 1 + 'a';
}
// Using DFS to find a connected component and collect all point coordinates
// 使用DFS找连通分量并收连通分量里所有点的坐标
void dfs(int x, int y, vector<P>& component) {
if (x < 0 || y < 0 || x == n || y == m || g[y][x] == '0')
return;
g[y][x] = '0'; // mark as seen;
component.emplace_back(x, y);
for (const auto& d : dirs)
dfs(x + d[0], y + d[1], component);
}
int main(void) {
cin >> n >> m;
for (int y = 0; y < m; ++y) cin >> g[y];
for (int y = 0; y < m; ++y) {
for (int x = 0; x < n; ++x) {
if (g[y][x] == '1') {
vector<P> component;
dfs(x, y, component);
char id = get_componentID(component);
for (const auto& [x, y] : component)
g[y][x] = id;
}
}
}
for (int y = 0; y < m; ++y) {
for (int x = 0; x < n; ++x) cout << g[y][x];
cout << endl;
}
}