AcWing1402.星空之夜

【题目链接】1402. 星空之夜 - AcWing题库

夜空深处,闪亮的星星以星群的形式出现在人们眼中,形态万千。

一个星群是指一组非空的在水平,垂直或对角线方向相邻的星星的集合。

一个星群不能是一个更大星群的一部分。

星群可能是相似的。

如果两个星群的形状、包含星星的数目相同,那么无论它们的朝向如何,都认为它们是相似的。

通常星群可能有 8 种朝向,如下图所示:

starry-1.gif

现在,我们用一个二维 01矩阵来表示夜空,如果一个位置上的数字是 1,那么说明这个位置上有一个星星,否则这个位置上的数字应该是 0。

给定一个夜空二维矩阵,请你将其中的所有星群用小写字母进行标记,标记时相似星群用同一字母,不相似星群用不同字母。

标注星群就是指将星群中所有的 1 替换为小写字母。

输入样例:
23
15
10001000000000010000000
01111100011111000101101
01000000010001000111111
00000000010101000101111
00000111010001000000000
00001001011111000000000
10000001000000000000000
00101000000111110010000
00001000000100010011111
00000001110101010100010
00000100110100010000000
00010001110111110000000
00100001110000000100000
00001000100001000100101
00000001110001000111000
输出样例:
a000a0000000000b0000000
0aaaaa000ccccc000d0dd0d
0a0000000c000c000dddddd
000000000c0b0c000d0dddd
00000eee0c000c000000000
0000e00e0ccccc000000000
b000000e000000000000000
00b0f000000ccccc00a0000
0000f000000c000c00aaaaa
0000000ddd0c0b0c0a000a0
00000b00dd0c000c0000000
000g000ddd0ccccc0000000
00g0000ddd0000000e00000
0000b000d0000f000e00e0b
0000000ddd000f000eee000
样例解释

样例对应的星空图如下:

starry-2.gif

答案对应的标记后星空图如下:

starry-3.gif

 【代码及详细注释】

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const double eps=1e-8;
const int N=150;
char mp[N][N];
PII q[200];
int n,m,cnt=0,top;//top用于存储每个星群中点的数量 
double hash_val[30];
bool check(int x,int y)
{
	if(x<0||x>=n||y<0||y>=m) return false;//下标越界 
	else if(mp[x][y]=='0') return false;//已经遍历过或者不是星群 
	return true;
}
void dfs(int x,int y)//找出当前的连通块
{
	q[top++]={x,y};//存储每个星群中的点
	mp[x][y]='0';//进行标记防止重复遍历
	for(int i=x-1;i<=x+1;i++)
	{
		for(int j=y-1;j<=y+1;j++)
		{
			if(check(i,j))//判断位置是否是星群中的一点及位置是否合法 
				dfs(i,j);//继续深搜遍历 
		}
	 } 
 } 
 double get_dist(int a,int b)
 {
 	PII aa=q[a],bb=q[b];
 	double xx=aa.first-bb.first;
 	double yy=aa.second-bb.second;
 	return sqrt(xx*xx+yy*yy);
 }
double get_hash()
{
	double ans=0;
	for(int i=0;i<top;i++)
	{
		for(int j=0;j<i;j++)
			ans+=get_dist(i,j);//获取两个点的欧几里得距离值 
	}
	return ans;//返回这个星群映射出的所有点之间的距离值 
}
char get_id()
{
	double val=get_hash();
	for(int i=0;i<cnt;i++)//从已有的星群中查找是否有一样的
	{
		if(abs(val-hash_val[i])<eps)
			return 'a'+i;
	 } 
	hash_val[cnt++]=val;//是一个新的星群
	return 'a'+cnt-1; 
}
int main()
{
	cin>>m>>n;
	for(int i=0;i<n;i++) scanf("%s",mp[i]);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(mp[i][j]=='1')//出现了一个新的星群
			{
				top=0;
				dfs(i,j);
				char id=get_id();//获取当前星群的编号 
				for(int k=0;k<top;k++)
					mp[q[k].first][q[k].second]=id;//对星群中所有的点编号 
			} 
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
			cout<<mp[i][j];
		cout<<endl;
	}
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519095.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用git 和 github协作开发

文章目录 github浏览器汉化插件github新建仓库git安装以及ssh配置团队创建及基本命令的使用创建团队基本命令 分支管理快速切换远程仓库地址 如何使用git && github进行协作开发&#xff0c;包括git常见基础命令 github浏览器汉化插件 在刚开始使用github的时候&#…

python函数练习2

找出10000以内能被5或6整除&#xff0c;但不能被两者同时整除的数&#xff08;函数&#xff09; def func():for i in range(1,50):if (i % 5 0 or i % 6 0 ):if i % 5 0 and i % 6 0:continue #利用continue跳过能被5和6整除的数print(i) func()写一个方法&#xff0c;计算…

OriginCar之FoxGlove使用

OriginCar之FoxGlove使用 前言 OriginCar自带一套用于智能车比赛的上位机数字系统&#xff0c;用于监控OriginCar各个传感器信息以及和OriginCar进行话题服务通信&#xff0c;使用者可以下载百度网盘中关于数字环境使用文档及启动文件的相关内容。以下是上位机介绍。 传感器…

2.Swift基础控件:图标文字按钮

Swift图标标题按钮 一、自定义IconTitleButton类 import Foundation/* 枚举 设置 图片的位置 */ enum ButtonImagePosition : Int {case imageTop 0case imageLeftcase imageBottomcase imageRight } extension UIButton {/**type &#xff1a;image 的位置Space &#xff1…

Arcgis Pro地理配准

目录 一、目的 二、配准 1、找到配准工具 2、添加控制点 3、选择控制点 4、添加更多控制点 5、配准完成、保存 三、附录 1、查看控制点或删除控制点 2、效果不好怎么办 一、目的 下面我们将两张地图进行配准&#xff0c;其中一张有地理位置&#xff0c;而另外一张没…

nvm保姆级安装使用教程

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 开发环境篇 ✨特色专栏&#xff1a; M…

java -网络编程socket-聊天室-02

完整版代码 java -聊天室的代码: 用于存放聊天室的项目的代码和思路导图https://gitee.com/to-uphold-justice-for-others/java---code-for-chat-rooms.git 先引入线程的正统解释 线程&#xff08;Thread&#xff09;是程序执行流的最小单元。线程是操作系统分配CPU时间片的基…

导入项目运行后,报错java: Cannot find JDK ‘XX‘ for module ‘XX‘

解决方案&#xff1a; 1、删除.idea和.iml文件 2、右击此module&#xff0c;点击 Open Module Settings 在 Module SDK 中选择所安装的java版本后&#xff0c;点击右下角 Apply 3、再运行试试吧&#xff0c;成功&#xff01;

《QT实用小工具·十四》面板容器控件和图形字体示例

1、概述 源码放在文章末尾 面板容器控件包含如下功能&#xff1a; 支持所有widget子类对象&#xff0c;自动产生滚动条。 支持自动拉伸自动填充。 提供接口获取容器内的所有对象的指针。 可设置是否自动拉伸宽度高度。 可设置设备面板之间的间距和边距。 超级图形字体类…

金陵科技学院软件工程学院软件工程专业

感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦~~ 感兴趣的小伙伴可以私信我哦~~ 是笔者写的各种高质量作业和实验哦…

【美团笔试题汇总】2023-08-26-美团春秋招笔试题-三语言题解(CPP/Python/Java)

&#x1f36d; 大家好这里是KK爱Coding &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新小米近期的春秋招笔试题汇总&#xff5e; &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f…

在线除背景抠图工具推荐,通过AI自动去除人物背景,给图片背景换色

发现了一个好的在线除水印的网站&#xff0c;这里由「易极赞」的小编来分享给大家。它就是我们今天的主角SnapEdit。 工具简介 SnapEdit 借助至极先进的人工智能技术&#xff0c;得以自动判别图像的主体与背景&#xff0c;飞速地移除背景且保留主体的细微之处和边缘轮廓&…

十六.PyEcharts常用视图(2)

目录 一.饼图 二.空心饼图(掏空) 三.玫瑰图 四.修改图例位置--全局 五.雷达图 六.时间轴 简单写一下,快速出图... 一.饼图 #饼图 import pyecharts.options as opts from pyecharts.faker import Faker from pyecharts.charts import Pie #zip() data_pie list(zip(Fa…

Floyd之蓝桥公园

Floyd Floyd算法是一种用于解决“所有点最短路径”问题的算法。这是一个动态规划算法&#xff0c;可以在任何包含向量和非负权重的图中使用。它的时间复杂度是&#xff0c;其中是图中的节点数。 首先&#xff0c;我们定义一个二维数组表示从到的最短距离&#xff0c;初始时如…

软著说明文档生成/辅助填写工具

软著说明文档生成/辅助填写工具&#xff0c;自行申请软著的话&#xff0c;软著60页源码还比较容易搞定&#xff0c;但是说明文档有格式和字数要求&#xff0c;就很烦。这个网站可以进行格式和内容的辅助填写&#xff0c;不用再把精力浪费到没用的调整格式上&#xff0c;网站地址…

揭秘SCQL:隐私计算的未来之路

1.SCQL使用/集成最佳实践 隐语隐私计算中SCQL&#xff08;Secure Collaborative Query Language&#xff09;的设计旨在提供一种便捷且安全的方式来处理多方参与下的隐私敏感数据查询与分析&#xff0c;而无需暴露原始数据给任何一方。以下是基于以上所记录信息的SCQL使用和集…

Jackson @JsonUnwrapped注解扁平化 序列化反序列化数据

参考资料 Jackson 2.x 系列【7】注解大全篇三JsonUnwrapped 以扁平的数据结构序列化/反序列化属性Jackson扁平化处理对象 目录 一. 前期准备1.1 前端1.2 实体类1.3 Controller层 二. 扁平化序列反序列化数据2.1 序列化数据2.2 反序列化数据 三. 前缀后缀处理属性同名四. Map数…

Pillow教程10:设计博文的文字背景封面图,再也不担心找不到不素材了

---------------Pillow教程集合--------------- Python项目18&#xff1a;使用Pillow模块&#xff0c;随机生成4位数的图片验证码 Python教程93&#xff1a;初识Pillow模块&#xff08;创建Image对象查看属性图片的保存与缩放&#xff09; Pillow教程02&#xff1a;图片的裁…

C#中ref和out相关知识点

知识点一&#xff1a; 知识点二&#xff1a; 知识点三&#xff1a; 测试&#xff1a; 总结&#xff1a; 练习

逐步学习Go-WaitGroup【连字都懒得写了,直接Show my Code】

package waitgroup_testimport ("fmt""runtime""sync""testing""time""github.com/stretchr/testify/assert" )// 这是对Go语标准库中sync包下的WaitGroup的描述。// WaitGroup用于等待一组并发的goroutine结结束…