有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);}}
}