正方形(Squares, ACM/ICPC World Finals 1990, UVa201)rust解法

有n行n列(2≤n≤9)的小黑点,还有m条线段连接其中的一些黑点。统计这些线段连成了多少个正方形(每种边长分别统计)。
行从上到下编号为1~n,列从左到右编号为1~n。边用H i j和V i j表示,分别代表边
(i,j)-(i,j+1)和(i,j)-(i+1,j)。如图4-5所示最左边的线段用V 1 1表示。图中包含两个边长为1的正方形和一个边长为2的正方形。
在这里插入图片描述

样例

4 
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 1 2
V 1 4
V 2 2
V 2 3
V 2 4
V 3 2
V 3 4
2 squre of len 1
1 squre of len 2

分析:
把所有边存到集合里。
对每一种正方形长度,遍历所有点,看集合里是否包含构成正方形的所有边。

解法:

use std::{io, collections::HashSet};fn main() {let mut buf = String::new();io::stdin().read_line(&mut buf).unwrap();let n: u32 = buf.trim().parse().unwrap();let mut buf = String::new();io::stdin().read_line(&mut buf).unwrap();let m: u32 = buf.trim().parse().unwrap();let mut bian= HashSet::new();for _i in 0..m {let mut buf = String::new();io::stdin().read_line(&mut buf).unwrap();let mut it = buf.split_whitespace();let t = it.next().unwrap().chars().nth(0).unwrap();let x: u32 = it.next().unwrap().parse().unwrap();let y: u32 = it.next().unwrap().parse().unwrap();bian.insert((t, x, y));}//println!("{:?}", bian);for len in 1..n {let mut cnt = 0;for i in 1..=n-len{'foo: for j in 1..=n-len{//println!("len: {}, i,j: {},{}", len, i, j);for step in 0..len {let one = ('H', i, j + step);if !bian.contains(&one) {//println!("{:?}", one);continue 'foo;}let one = ('H', i + len, j + step);if !bian.contains(&one) {//println!("{:?}", one);continue 'foo;}let one = ('V', i + step, j);if !bian.contains(&one) {//println!("{:?}", one);continue 'foo;}let one = ('V', i + step, j + len);if !bian.contains(&one) {//println!("{:?}", one);continue 'foo;}}cnt += 1;}}if cnt > 0 {println!("{} squre of len {}", cnt, len);}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深度学习零基础教程

代码运行软件安装: anaconda:一个管理环境的软件–>https://blog.csdn.net/scorn_/article/details/106591160(可选装) pycharm:一个深度学习运行环境–>https://blog.csdn.net/scorn_/article/details/106591160&#xf…

2023/10/30-LED灯驱动开发

k1.c #include <linux/init.h> #include <linux/module.h> #include <linux/fs.h> #include <linux/uaccess.h> #include <linux/io.h> #include "head.h" char kbuf[128] {}; unsigned int major; //定义三个指针指向映射后的虚拟内…

家庭燃气表微信抄表识别系统

1.背景需求 目前家里燃气度数的读数上报&#xff0c;每个月在社区微信群里面将手机拍摄的燃气表读数截图&#xff08;加住址信息水印&#xff09;&#xff0c;发到群里给抄表员。 2.总体设计 设计目标 功能一&#xff1a;手机上随时可以远程采集读数图片&#xff08;自动加住…

单片机郭天祥(02)

1&#xff1a;解决keil5软件的乱码问题&#xff0c;修改编码为UTF-8 2&#xff1a;打开keil5使用debug对编写好的程序进行调试 给程序打上断点 使用仿真芯片 更改设备管理器相关设置 接通电源后点击debug连接到51单片机 使用stc-isp获取延时函数 将延时函数添加进入创建好的…

云计算与云服务

云计算与大数据 1、虚拟化简介1.1、什么是虚拟化1.2、虚拟化的分类 2、云计算与云服务2.1、云计算2.2、云服务2.3、云计算的特点 3、云服务模式&#xff08;IaaS、PaaS、SaaS和DaaS&#xff09;4、云计算分类&#xff08;公有云、私有云和混合云&#xff09; 1、虚拟化简介 当下…

高斯分布与高斯过程

一元高斯分布 我们从最简单最常见的一元高斯分布开始&#xff0c;其概率密度函数为&#xff1a; p ( x ) 1 σ 2 π e x p ( − ( x − μ ) 2 2 σ 2 ) p(x)\frac{1}{\sigma\sqrt{2\pi}}exp(-\frac{(x-\mu)^2}{2\sigma^2}) p(x)σ2π ​1​exp(−2σ2(x−μ)2​) 其中 μ \…

【大数据】Kafka 实战教程(一)

Kafka 实战教程&#xff08;一&#xff09; 1.Kafka 介绍1.1. 主要功能1.2. 使用场景1.3 详细介绍1.3.1 消息传输流程1.3.2 Kafka 服务器消息存储策略1.3.3 与生产者的交互1.3.4 与消费者的交互 2.Kafka 生产者3.Kafka 消费者3.1 Kafka 消费模式3.1.1 At-most-once&#xff08;…

FPGA设计FIR滤波器低通滤波器,代码及视频

名称&#xff1a;FIR滤波器低通滤波器 软件&#xff1a;Quartus 语言&#xff1a;Verilog/VHDL 本资源含有verilog及VHDL两种语言设计的工程&#xff0c;每个工程均可实现以下FIR滤波器的功能。 代码功能&#xff1a; 设计一个8阶FIR滤波器&#xff08;低通滤波器&#xff…

【试题040】多个逻辑或例题2

1.题目&#xff1a;设int n0;&#xff0c;执行表达式n ||(n-1) ||(n0)||(n1)||(n2)后n的值是 &#xff1f; 2.代码解析&#xff1a; 逻辑或 || 运算符是一个短路运算符&#xff0c;它从左到右依次计算表达式&#xff0c;如果遇到一个为真&#xff08;非零&#xff09;的值&am…

SequenceFile、元数据操作与MapReduce单词计数

文章目录 SequenceFile、元数据操作与MapReduce单词计数一、实验目标二、实验要求三、实验内容四、实验步骤附&#xff1a;系列文章 SequenceFile、元数据操作与MapReduce单词计数 一、实验目标 熟练掌握hadoop操作指令及HDFS命令行接口掌握HDFS SequenceFile读写操作掌握Map…

2021年03月 Python(三级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python编程&#xff08;1~6级&#xff09;全部真题・点这里 一、单选题&#xff08;共25题&#xff0c;每题2分&#xff0c;共50分&#xff09; 第1题 下列代码的输出结果是&#xff1f;&#xff08; &#xff09; x 0x10print(x)A&#xff1a;2 B&#xff1a;8 C&#xff…

数据结构:二叉树(2)

二叉树的基本操作 获取树的结点总数 遍历思路&#xff1a; 每次遍历一个节点&#xff0c;遍历完nodeSize&#xff0c;然后遍历它的左右子树 如果遍历到空的节点&#xff0c;就返回0 public int nodeSize 0;int size(TreeNode root){if(root null){return 0;}nodeSize;siz…

LeetCode讲解篇之77. 组合

文章目录 题目描述题解思路题解代码 题目描述 题解思路 遍历nums&#xff0c;让当前数字添加到结果前缀中&#xff0c;递归调用&#xff0c;直到前缀的长度为k&#xff0c;然后将前缀添加到结果集 题解代码 func combine(n int, k int) [][]int {var nums make([]int, n)fo…

【MATLAB源码-第51期】基于matlab的粒子群算法(PSO)的栅格地图路径规划。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 粒子群算法&#xff08;Particle Swarm Optimization&#xff0c;简称PSO&#xff09;是一种模拟鸟群觅食行为的启发式优化方法。以下是其详细描述&#xff1a; 基本思想&#xff1a; 鸟群在寻找食物时&#xff0c;每只鸟都会…

arrow(c++)改写empyrical系列1---用arrow读取基金净值数据并计算夏普率

用arrow c版本读取了csv中的基金净值数据&#xff0c;然后计算了夏普率&#xff0c;比较尴尬的是&#xff0c;arrow c版本计算耗费的时间却比python的empyrical版本耗费时间多。。。 arrow新手上路&#xff0c;第一次自己去实现功能&#xff0c;实现的大概率并不是最高效的方…

windows上下载github上的linux内核项目遇到的问题

问题一&#xff1a;clone的时候报错 Cloning into G:\github\linux... POST git-upload-pack (gzip 27925 to 14032 bytes) remote: Counting objects: 6012062, done. remote: Compressing objects: 100% (1031/1031), done. remote: Total 6012062 (delta 893), reused 342 (…

【Axure高保真原型】可视化图表图标

今天和粉丝们免费分享可视化图表图标原型模板&#xff0c;包括柱状图、条形图、环形图、散点图、水波图等常用的可视化图表图标。 【原型效果】 【原型预览】 https://axhub.im/ax9/d402c647c82f9185/#c1 【原型下载】 这个模板可以在 Axure高保真原型哦 小程序里免费下载哦…

0基础学习VR全景平台篇第110篇:源图像导入和镜头预设 - PTGui Pro教程

上课&#xff01;全体起立~ 大家好&#xff0c;欢迎观看蛙色官方系列全景摄影课程&#xff01; 本节教程&#xff0c;我们讲述拼接软件 PTGui Pro 操作的第一步&#xff1a;导入源图像和预设镜头&画幅参数。 我们此次课堂有两个重点&#xff1a; 第一点是 培养摄影后期…

HTTPS、SSL/TLS,HTTPS运行过程,RSA加密算法,AES加密算法

1、为什么网站要使用安全证书 我们所处的网络环境是复杂多样的&#xff0c;大致分为两类&#xff0c;一类是可信的网络服务商&#xff0c;比如直接连的电信运营商的网络&#xff0c;网线&#xff0c;4G&#xff0c;5G&#xff1b;另一类是不可信的网络&#xff0c;比如WIFI&am…

会声会影2024有哪些新功能?好不好用

比如会声会影视频编辑软件&#xff0c;既加入光影、动态特效的滤镜效果&#xff0c;也提供了与色彩调整相关的LUT配置文件滤镜&#xff0c;可选择性大&#xff0c;运用起来更显灵活。会声会影在用户的陪伴下走过20余载&#xff0c;经过上百个版本的优化迭代&#xff0c;已将操作…