首页 > 其他分享 >【哈希---图像存储】星空之夜

【哈希---图像存储】星空之夜

时间:2023-02-09 17:34:38浏览次数:65  
标签:星空 int double --- ++ 哈希 星群 size

题目:

夜空深处,闪亮的星星以星群的形式出现在人们眼中,形态万千。一个星群是指一组非空的在水平,垂直或对角线方向相邻的星星的集合。一个星群不能是一个更大星群的一部分。星群可能是相似的。如果两个星群的形状、包含星星的数目相同,那么无论它们的朝向如何,都认为它们是相似的。通常星群可能有 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

相关文章

  • 深度复盘-重启 etcd 引发的异常
    作者信息:唐聪、王超凡,腾讯云原生产品中心技术专家,负责腾讯云大规模TKE集群和etcd控制面稳定性、性能和成本优化工作。王子勇,腾讯云专家级工程师,腾讯云计算产品技术......
  • React面试题---setState是同步执行还是异步执行?
    1.React中setState是同步执行还是异步执行?什么时候是同步什么时候是异步?1importReact,{Component}from"react";2importReactDOMfrom"react-dom";3//......
  • springcloud(四) - 服务治理Hystrix
    功能介绍调用下游服务,下游因为超时、异常等原因报错的时候。hystrix保证不会出现整体异常,避免雪崩。主要策略是服务的熔断、降级 应用场景降级:异常、超时、熔断等情况......
  • [threeJS]--- 外部导入的模型如何编程式实现帧动画以及调用模型自带的动画
    1.代码中编写帧动画并且调用 asyncfunctionkeyframeAni(object){consttimes=[0,2];//关键帧时间数组,单位'秒'constrorateValues=[0,-Math.PI*2];......
  • qiankun -- 微前端
    1.环境vue2.x@vue/cli5.0.8node16.18.02.搭建:使用vuecreate创建2个vue项目:qiankun-base,qiankun-subapp配置可参照官网及互联网资料进行。遇到的问题:在主应用......
  • springcloud(二) - 服务调用Feign&openFeign
    功能介绍:动态代理的方式,简化请求其他服务的开发成本,更好得对请求地址组装、接受返回信息、返回参数解析等  Feign和OpenFeign区别:OpenFeign实现了Feign的基础功能,同......
  • springcloud(三) - 负载均衡Ribbon
    功能介绍基本保证每个服务不同的ip接收到的请求数量是一样的,确保在微服务下没有没有那个服务器负载过多而另外一个闲置。IRule:根据规则获取制定的服务  规则列表R......
  • 好客租房5-React脚手架的应用
    3.1react脚手架意义1脚手架是开发现代web应用的必备2充分利用webpackbabeleslint等工具进行使用3零配置4关注业务即可3.2使用react脚手架初始化项目1初始化项目命令:npx......
  • 好客租房2-React概述
    1.1什么是reactReact是一个用于构建用户界面的javascript库用户界面:HTML页面React主要用来HTML或者沟通构建web应用如果从MVC的角度来看react仅仅是从视图层也就是只负......
  • element el-table固定列凹陷问题
    1、业务背景列表显示字段过多,最后一栏操作列加固定显示,横向添加滚动条,在自测浏览器开发者模式时,发现固定列的最后一行出现了凹陷现象,网上查阅资料大多为在更新生命周期或者......