正方形（Squares, ACM/ICPC World Finals 1990, UVa201）rust解法

本文主要是介绍正方形（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);}}
}

这篇关于正方形（Squares, ACM/ICPC World Finals 1990, UVa201）rust解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---