题目:
夜空深处,闪亮的星星以星群的形式出现在人们眼中,形态万千。一个星群是指一组非空的在水平,垂直或对角线方向相邻的星星的集合。一个星群不能是一个更大星群的一部分。星群可能是相似的。如果两个星群的形状、包含星星的数目相同,那么无论它们的朝向如何,都认为它们是相似的。通常星群可能有 8 种朝向,如下图所示:
现在,我们用一个二维 01 矩阵来表示夜空,如果一个位置上的数字是1,那么说明这个位置上有一个星星,否则这个位置上的数字应该是 0。给定一个夜空二维矩阵,请你将其中的所有星群用小写字母进行标记,标记时相似星群用同一字母,不相似星群用不同字母。标注星群就是指将星群中所有的 1 替换为小写字母。
输入格式: 第一行包含一个整数 W,表示矩阵宽度。
第二行包含一个整数 H,表示矩阵高度。
接下来 H 行,每行包含一个长度为 W 的 01 序列,用来描述整个夜空矩阵。
输出格式: 输出标记完所有星群后的二维矩阵。用小写字母标记星群的方法很多,我们将整个输出读取为一个字符串,能够使得这个字符串字典序最小的标记方式,就是我们想要的标记方式。输出这个标记方式标出的最终二维矩阵。
数据范围: 0≤W,H≤100 0≤星群数量≤500 0≤不相似星群数量≤26 1≤星群中星星的数量≤160
题解:
这道题的主要难点是如何判断两个连通块是否是相似的,即如何存储图像。
可以通过计算连通块中每两个点之间的欧式距离,并把它们全部加起来,加起来的这个值就是这个图形的哈希值。
题解:
#include <iostream> #include <cmath> #define x first #define y second using namespace std; using PII = pair<int, int>; const int N = 110; const double eps = 1e-6; int n, m; char g[N][N]; PII q[N * N]; double get_dist(PII a, PII b) { double dx = a.x - b.x, dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } // 算一下当前q数组里存的1连通块的哈希值 double get_hash(int size) { double sum = 0; for (int i = 0; i < size; i++) for (int j = i + 1; j < size; j++) sum += get_dist(q[i], q[j]); return sum; } // 根据这个哈希值,返回其应该被标记为什么字母 char get_id(double key) { static double hash[30]; static int id = 0; for (int i = 0; i < id; i++) // 如果该哈希值已存在,则返回之前给它配的那个字母 if (abs(hash[i] - key) < eps) return i + 'a'; // 否则将该哈希值加入数组,并返回下一个还没使用的字母 hash[id++] = key; return id - 1 + 'a'; } void dfs(int x, int y, int& size) { q[size++] = {x, y}; g[x][y] = '0'; for (int a = x - 1; a <= x + 1; a++) for (int b = y - 1; b <= y + 1; b++) { if (a == x && b == y) continue; if (0 <= a && a < m && 0 <= b && b < n && g[a][b] == '1') dfs(a, b, size); } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) cin >> g[i]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == '1') { int size = 0; dfs(i, j, size); char c = get_id(get_hash(size)); for (int k = 0; k < size; k++) g[q[k].x][q[k].y] = c; } for (int i = 0; i < m; i++) cout << g[i] << endl; }
标签:星空,int,double,---,++,哈希,星群,size From: https://www.cnblogs.com/hhhhy0420/p/17106397.html