-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.rs
65 lines (57 loc) · 1.89 KB
/
main.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
use std::collections::VecDeque;
use std::io::prelude::*;
use std::io::stdin;
fn main() {
let mut queue: VecDeque<(usize, usize, i32)> = VecDeque::new();
let garden = stdin()
.lock()
.lines()
.enumerate()
.map(|(i, line)| {
line.unwrap()
.chars()
.enumerate()
.map(|(j, ch)| {
if ch == 'S' {
queue.push_back((i, j, 0));
true
} else {
ch == '.'
}
})
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
const DIRS: [(usize, usize); 4] = [(0, 1), (0, usize::MAX), (1, 0), (usize::MAX, 0)];
let (m, n) = (garden.len(), garden[0].len());
let mut visited = vec![vec![-1; n]; n];
const STEPS: usize = 26501365;
let p = STEPS % 2;
while let Some((i, j, mut step)) = queue.pop_front() {
if visited[i][j] != -1 {
continue;
}
visited[i][j] = step;
step += 1;
for &(di, dj) in &DIRS {
let (x, y) = (i + di, j + dj);
if x < m && y < n && garden[x][y] && visited[x][y] == -1 {
queue.push_back((x, y, step));
}
}
}
let values = visited
.iter()
.flatten()
.filter(|&&x| x != -1)
.map(|&x| x as usize)
.collect::<Vec<_>>();
let copies = (STEPS - n / 2) / n;
let odd = values.iter().filter(|&&x| x % 2 == p).count();
let even = values.iter().filter(|&&x| x % 2 != p).count();
let o_corner = values.iter().filter(|&&x| x % 2 == p && x > n / 2).count();
let e_corner = values.iter().filter(|&&x| x % 2 != p && x > n / 2).count();
let ans = (copies + 1).pow(2) * odd + copies.pow(2) * even - (copies + 1) * o_corner
+ copies * e_corner;
println!("{}", ans);
}