Submission #5913342
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 mut 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
2019-06-15 14:45:35+0900
Task
F - Lotus Leaves
User
ryoryoryo111
Language
Rust (1.15.1)
Score
0
Code Size
3707 Byte
Status
WA
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;
| ^^^^^^^
warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
--> ./Main.rs:60:9
|
60 | let mut ans = solver.max_flow(h + w, h + w + 1);
| ^^^^^^^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 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
WA
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
WA
3 ms
4352 KB
1_42.txt
AC
2 ms
4352 KB
1_43.txt
WA
2 ms
4352 KB
1_44.txt
AC
2 ms
4352 KB
1_45.txt
WA
2 ms
4352 KB
1_46.txt
WA
2 ms
4352 KB
1_47.txt
AC
2 ms
4352 KB
1_48.txt
WA
2 ms
4352 KB
1_49.txt
AC
2 ms
4352 KB