Submission #5913372
Source Code Expand
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;
#[allow(unused_macros)]
macro_rules! debug {
($($e:expr),*) => {
#[cfg(debug_assertions)]
$({
let (e, mut err) = (stringify!($e), std::io::stderr());
writeln!(err, "{} = {:?}", e, $e).unwrap()
})*
};
}
fn main() {
let v = read_vec::<usize>();
let (h, w) = (v[0], v[1]);
let mut grid = vec![vec![]; h];
for y in 0..h {
grid[y] = read::<String>().chars().collect::<Vec<_>>();
}
let mut start_x = 0usize;
let mut start_y = 0usize;
let mut goal_x = 0usize;
let mut goal_y = 0usize;
for y in 0..h {
for x in 0..w {
if grid[y][x] == 'S' {
start_y = y;
start_x = x;
} else if grid[y][x] == 'T' {
goal_y = y;
goal_x = x;
}
}
}
// [0 ~ w - 1]. [w ~ w + h - 1] [h + w]: start, [h + w + 1]]: goal
let mut solver = Solver::new(h + w + 2);
let mut inf = 1000_000_000;
// to _start
solver.add_edge_both(start_x, h + w, inf);
solver.add_edge_both(w + start_y, h + w, inf);
// to_goal
solver.add_edge_both(goal_x, h + w + 1, inf);
solver.add_edge_both(w + goal_y, h + w + 1, inf);
for y in 0..h {
for x in 0..w {
if grid[y][x] == 'o' {
solver.add_edge_both(x, w + y, 1);
}
}
}
let ans = solver.max_flow(h + w, h + w + 1);
if ans >= inf {
println!("-1");
return;
}
println!("{:?}", ans);
}
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[derive(Clone, Copy)]
struct Edge {
to: usize,
cap: i64,
rev: usize,
}
#[derive(Clone)]
struct Solver {
edges: Vec<Vec<Edge>>,
used: Vec<bool>,
}
impl Solver {
fn new(v: usize) -> Solver {
Solver {
edges: vec![Vec::new(); v],
used: vec![false; v],
}
}
fn add_edge_both(&mut self, from: usize, to: usize, cap: i64) {
self.add_edge(from, to, cap);
self.add_edge(to, from, cap);
}
fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
let rev = self.edges[to].len();
self.edges[from].push(Edge {
to: to,
cap: cap,
rev: rev,
});
let rev = self.edges[from].len() - 1;
self.edges[to].push(Edge {
to: from,
cap: 0,
rev: rev,
});
}
fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
if v == t {
return f;
}
self.used[v] = true;
for i in 0..self.edges[v].len() {
let edge = self.edges[v][i];
if !self.used[edge.to] && edge.cap > 0 {
let d = self.dfs(edge.to, t, std::cmp::min(f, edge.cap));
if d > 0 {
self.edges[v][i].cap -= d;
self.edges[edge.to][edge.rev].cap += d;
return d;
}
}
}
0
}
fn max_flow(&mut self, s: usize, t: usize) -> i64 {
let mut flow = 0;
loop {
self.used = vec![false; self.edges.len()];
let f = self.dfs(s, t, std::i64::MAX);
if f == 0 {
return flow;
}
flow += f;
}
}
}
Submission Info
Submission Time |
|
Task |
F - Lotus Leaves |
User |
ryoryoryo111 |
Language |
Rust (1.15.1) |
Score |
800 |
Code Size |
3703 Byte |
Status |
AC |
Exec Time |
13 ms |
Memory |
4352 KB |
Compile Error
warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
--> ./Main.rs:43:9
|
43 | let mut inf = 1000_000_000;
| ^^^^^^^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
4352 KB |
0_01.txt |
AC |
2 ms |
4352 KB |
0_02.txt |
AC |
2 ms |
4352 KB |
0_03.txt |
AC |
2 ms |
4352 KB |
1_00.txt |
AC |
2 ms |
4352 KB |
1_01.txt |
AC |
2 ms |
4352 KB |
1_02.txt |
AC |
2 ms |
4352 KB |
1_03.txt |
AC |
2 ms |
4352 KB |
1_04.txt |
AC |
2 ms |
4352 KB |
1_05.txt |
AC |
2 ms |
4352 KB |
1_06.txt |
AC |
13 ms |
4352 KB |
1_07.txt |
AC |
2 ms |
4352 KB |
1_08.txt |
AC |
2 ms |
4352 KB |
1_09.txt |
AC |
5 ms |
4352 KB |
1_10.txt |
AC |
2 ms |
4352 KB |
1_11.txt |
AC |
2 ms |
4352 KB |
1_12.txt |
AC |
2 ms |
4352 KB |
1_13.txt |
AC |
3 ms |
4352 KB |
1_14.txt |
AC |
3 ms |
4352 KB |
1_15.txt |
AC |
2 ms |
4352 KB |
1_16.txt |
AC |
2 ms |
4352 KB |
1_17.txt |
AC |
2 ms |
4352 KB |
1_18.txt |
AC |
2 ms |
4352 KB |
1_19.txt |
AC |
3 ms |
4352 KB |
1_20.txt |
AC |
2 ms |
4352 KB |
1_21.txt |
AC |
2 ms |
4352 KB |
1_22.txt |
AC |
2 ms |
4352 KB |
1_23.txt |
AC |
3 ms |
4352 KB |
1_24.txt |
AC |
2 ms |
4352 KB |
1_25.txt |
AC |
2 ms |
4352 KB |
1_26.txt |
AC |
2 ms |
4352 KB |
1_27.txt |
AC |
2 ms |
4352 KB |
1_28.txt |
AC |
2 ms |
4352 KB |
1_29.txt |
AC |
2 ms |
4352 KB |
1_30.txt |
AC |
2 ms |
4352 KB |
1_31.txt |
AC |
2 ms |
4352 KB |
1_32.txt |
AC |
5 ms |
4352 KB |
1_33.txt |
AC |
2 ms |
4352 KB |
1_34.txt |
AC |
2 ms |
4352 KB |
1_35.txt |
AC |
3 ms |
4352 KB |
1_36.txt |
AC |
2 ms |
4352 KB |
1_37.txt |
AC |
4 ms |
4352 KB |
1_38.txt |
AC |
2 ms |
4352 KB |
1_39.txt |
AC |
5 ms |
4352 KB |
1_40.txt |
AC |
2 ms |
4352 KB |
1_41.txt |
AC |
3 ms |
4352 KB |
1_42.txt |
AC |
2 ms |
4352 KB |
1_43.txt |
AC |
2 ms |
4352 KB |
1_44.txt |
AC |
2 ms |
4352 KB |
1_45.txt |
AC |
2 ms |
4352 KB |
1_46.txt |
AC |
2 ms |
4352 KB |
1_47.txt |
AC |
2 ms |
4352 KB |
1_48.txt |
AC |
2 ms |
4352 KB |
1_49.txt |
AC |
2 ms |
4352 KB |