fn main() { let mut io = IO::new(); input!{ from io, h: usize, w: usize, cho: [Chars; h] } let mut din = Dinic::new(); let mut edges = Vec::new(); for i in 0..h { for j in 0..w { if cho[i][j] == 'w' { din.add_edge(h*w, i*w+j, 1); if i > 0 && cho[i-1][j] == 'b' { let id = din.add_edge(i*w+j, i*w+j-w, 1); edges.push((id, i*w+j, i*w+j-w)); } if j > 0 && cho[i][j-1] == 'b' { let id = din.add_edge(i*w+j, i*w+j-1, 1); edges.push((id, i*w+j, i*w+j-1)); } if i + 1 < h && cho[i+1][j] == 'b' { let id = din.add_edge(i*w+j, i*w+j+w, 1); edges.push((id, i*w+j, i*w+j+w)); } if j + 1 < w && cho[i][j+1] == 'b' { let id = din.add_edge(i*w+j, i*w+j+1, 1); edges.push((id, i*w+j, i*w+j+1)); } } else if cho[i][j] == 'b' { din.add_edge(i*w+j, h*w+1, 1); } } } let mut ans = 0; din.max_flow(h*w, h*w+1); let mut used = vec![vec![false; w]; h]; for (id, u, v) in edges { if din.get_flow(&id) > 0 { used[u/w][u%w] = true; used[v/w][v%w] = true; ans += 100; } } let mut whi = 0; let mut bla = 0; for i in 0..h { for j in 0..w { if cho[i][j] == 'w' && !used[i][j] { whi += 1; } else if cho[i][j] == 'b' && !used[i][j] { bla += 1; } } } let p = std::cmp::min(whi, bla); ans += p * 10 + whi + bla - 2 * p; io.println(ans); } // ------------ Dinic's algorithm start ------------ use std::cmp::{max, min}; struct Edge { dst: usize, rev: usize, flow: F, upper: F, } #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug, Hash)] pub struct EdgeId(usize, usize); struct TemporaryData { n: usize, s: usize, t: usize, label: Vec, current_edge: Vec, buffer: Vec, } #[derive(Default)] pub struct Dinic { edges: Vec>>, } impl Dinic { pub fn new() -> Self { Self { edges: Vec::new() } } pub fn add_edge(&mut self, src: usize, dst: usize, capacity: F) -> EdgeId { let n = max(max(src, dst) + 1, self.edges.len()); self.edges.resize_with(n, || Vec::with_capacity(4)); let e = self.edges[src].len(); let re = self.edges[dst].len() + if src == dst { 1 } else { 0 }; self.edges[src].push(Edge { dst, rev: re, flow: F::zero(), upper: capacity, }); self.edges[dst].push(Edge { dst: src, rev: e, flow: capacity, upper: capacity, }); EdgeId(src, e) } fn prepare_data(&mut self, s: usize, t: usize) -> TemporaryData { let n = max(max(s, t) + 1, self.edges.len()); self.edges.resize_with(n, Default::default); TemporaryData { n, s, t, label: vec![0; n], current_edge: vec![0; n], buffer: Vec::with_capacity(n), } } fn dual(&self, data: &mut TemporaryData) -> bool { let n = data.n; data.label.iter_mut().for_each(|v| *v = n); data.current_edge.iter_mut().for_each(|v| *v = 0); let mut queue = std::mem::take(&mut data.buffer); queue.clear(); queue.push(data.s); data.label[data.s] = 0; let mut q_pos = 0; 'new_node: while q_pos < queue.len() { let u = queue[q_pos]; q_pos += 1; let next_label = data.label[u] + 1; for e in &self.edges[u] { if e.flow < e.upper && data.label[e.dst] == data.n { data.label[e.dst] = next_label; if e.dst == data.t { break 'new_node; } queue.push(e.dst); } } } data.buffer = queue; data.label[data.t] < n } #[allow(clippy::many_single_char_names)] fn primal_dfs(&mut self, u: usize, data: &mut TemporaryData, mut limit: F) -> F { if u == data.s { return limit; } let mut total = F::zero(); let mut i = data.current_edge[u]; while i < self.edges[u].len() { let e = &self.edges[u][i]; if e.flow.is_positive() && data.label[e.dst] < data.label[u] { let new_limit = min(limit, e.flow); let v = e.dst; let f = self.primal_dfs(v, data, new_limit); if !f.is_zero() { let e = &mut self.edges[u][i]; let v = e.dst; let r = e.rev; e.flow -= f; self.edges[v][r].flow += f; total += f; limit -= f; if limit.is_zero() { if self.edges[u][i].flow.is_zero() { i += 1; } data.current_edge[u] = i; return total; } } } i += 1; } data.current_edge[u] = !0; data.label[u] = data.n; total } pub fn augment(&mut self, s: usize, t: usize, limit: F) -> F { assert_ne!(s, t, "Source and sink vertex should be different"); let mut data = self.prepare_data(s, t); let mut flow = F::zero(); while self.dual(&mut data) { flow += self.primal_dfs(data.t, &mut data, limit - flow); if flow == limit { break; } } flow } pub fn max_flow(&mut self, s: usize, t: usize) -> (F, Vec) { assert_ne!(s, t, "Source and sink vertex should be different"); let mut data = self.prepare_data(s, t); let inf = self.edges[s] .iter() .map(|e| e.upper - e.flow) .fold(F::zero(), |a, b| a + b); let mut flow = F::zero(); while self.dual(&mut data) { flow += self.primal_dfs(data.t, &mut data, inf); } let label = std::mem::take(&mut data.label); let cut = label .into_iter() .enumerate() .filter(|(_, l)| l < &data.n) .map(|(i, _)| i) .collect(); (flow, cut) } pub fn get_flow(&self, e: &EdgeId) -> F { self.edges[e.0][e.1].flow } } // ------------ Dinic's algorithm start ------------ use std::fmt::Display; pub trait Cost: Element + Display + Clone + Copy + Eq + Ord + Zero + One + Add + AddAssign + Sub + Mul + Neg { fn is_positive(&self) -> bool { self > &Self::zero() } fn is_negative(&self) -> bool { self < &Self::zero() } const MAX: Self; } pub trait Flow: Cost + SubAssign { fn abs(&self) -> Self { if self.is_negative() { -*self } else { *self } } } macro_rules! impl_flow { ($($T:ident,)*) => { $( impl Flow for $T {} impl Cost for $T { const MAX: Self = std::$T::MAX; } )* }; } impl_flow!( i8, i16, i32, i64, i128, isize, ); // ------------ algebraic traits start ------------ use std::marker::Sized; use std::ops::*; /// 元 pub trait Element: Sized + Clone + PartialEq {} impl Element for T {} /// 結合性 pub trait Associative: Magma {} /// マグマ pub trait Magma: Element + Add {} impl> Magma for T {} /// 半群 pub trait SemiGroup: Magma + Associative {} impl SemiGroup for T {} /// モノイド pub trait Monoid: SemiGroup + Zero {} impl Monoid for T {} pub trait ComMonoid: Monoid + AddAssign {} impl ComMonoid for T {} /// 群 pub trait Group: Monoid + Neg {} impl> Group for T {} pub trait ComGroup: Group + ComMonoid {} impl ComGroup for T {} /// 半環 pub trait SemiRing: ComMonoid + Mul + One {} impl + One> SemiRing for T {} /// 環 pub trait Ring: ComGroup + SemiRing {} impl Ring for T {} pub trait ComRing: Ring + MulAssign {} impl ComRing for T {} /// 体 pub trait Field: ComRing + Div + DivAssign {} impl + DivAssign> Field for T {} /// 加法単元 pub trait Zero: Element { fn zero() -> Self; fn is_zero(&self) -> bool { *self == Self::zero() } } /// 乗法単元 pub trait One: Element { fn one() -> Self; fn is_one(&self) -> bool { *self == Self::one() } } macro_rules! impl_integer { ($($T:ty,)*) => { $( impl Associative for $T {} impl Zero for $T { fn zero() -> Self { 0 } fn is_zero(&self) -> bool { *self == 0 } } impl<'a> Zero for &'a $T { fn zero() -> Self { &0 } fn is_zero(&self) -> bool { *self == &0 } } impl One for $T { fn one() -> Self { 1 } fn is_one(&self) -> bool { *self == 1 } } impl<'a> One for &'a $T { fn one() -> Self { &1 } fn is_one(&self) -> bool { *self == &1 } } )* }; } impl_integer! { i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, } // ------------ algebraic traits end ------------ // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan(&mut self) -> ::Output { ::scan(self) } pub fn scan_vec(&mut self, n: usize) -> Vec<::Output> { (0..n).map(|_| self.scan::()).collect() } pub fn print(&mut self, x: T) { ::print(self, x); } pub fn println(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String); pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::().wrapping_sub(1) } } impl Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize, f32, f64); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------