AcWing 1402. 星空之夜
原题链接
中等
作者:
wjie
,
2021-01-28 12:01:59
,
所有人可见
,
阅读 459
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 105;
typedef pair<int, int> PII;
int n, m, hash_cnt, block_cnt;
char arr[N][N];
PII p[N * N];
double hash_code[30];
void dfs(int x, int y)
{
arr[x][y] = 0;
p[block_cnt++] = {x, y};
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 (i >= 0 && i < n && j >= 0 && j < m && arr[i][j] == '1') dfs(i, j);
}
}
}
double dist(PII a, PII b)
{
double dx = abs(a.first-b.first);
double dy = abs(a.second-b.second);
return sqrt(dx*dx + dy*dy);
}
double get_hash_code()
{
double res = 0;
for (int i = 0; i < block_cnt; ++i)
{
for (int j = i + 1; j < block_cnt; ++j)
{
res += dist(p[i], p[j]);
}
}
return res;
}
char get_id(double h)
{
for (int i = 0; i < hash_cnt; ++i)
{
if (fabs(hash_code[i]-h) < 1e-7)
{
return 'a' + i;
}
}
hash_code[hash_cnt++] = h;
return 'a' + hash_cnt-1;
}
int main()
{
scanf("%d%d", &m, &n);
for (int i = 0; i < n; ++i) scanf("%s", arr[i]);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (arr[i][j] == '1')
{
block_cnt = 0;
dfs(i, j);
double h = get_hash_code();
char c = get_id(h);
for (int k = 0; k < block_cnt; ++k) arr[p[k].first][p[k].second] = c;
}
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
printf("%c", arr[i][j]);
}
puts("");
}
return 0;
}