#![allow(non_snake_case)] #[allow(unused_macros)] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut tokens = $s.split_whitespace(); input_inner! { tokens, $($r)* } }; ($($r:tt)*) => { let s = { use std::io::Read; let mut res = String::new(); ::std::io::stdin().read_to_string(&mut res).unwrap(); res }; let mut tokens = s.split_whitespace(); input_inner! { tokens, $($r)* } }; } #[allow(unused_macros)] macro_rules! input_inner { ($tokens:expr) => {}; ($tokens:expr,) => {}; ($tokens:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($tokens, $t); input_inner! { $tokens $($r)* } }; } #[allow(unused_macros)] macro_rules! read_value { ($tokens:expr, ( $($t:tt),* )) => { ( $(read_value!($tokens, $t)),* ) }; ($tokens:expr, [ $t:tt; $len:expr ]) => { (0..$len).map(|_| read_value!($tokens, $t)).collect::>() }; ($tokens:expr, chars) => { read_value!($tokens, String).chars().collect::>() }; ($tokens:expr, usize1) => { read_value!($tokens, usize) - 1 }; ($tokens:expr, $t:ty) => { $tokens.next().unwrap().parse::<$t>().expect("parse error") }; } struct UnionFind { v: Vec, } impl UnionFind { fn new(size: usize) -> Self { let mut v = vec![0usize; size]; for i in 0..size { v[i] = i; } Self { v, } } fn root(&mut self, x: usize) -> usize { let parent = self.v[x]; if parent == x { return x; } let res = self.root(parent); self.v[x] = res; res } fn unite(&mut self, x: usize, y: usize) { let rootx = self.root(x); let rooty = self.root(y); self.v[rooty] = rootx; } } fn main() { input! { H: usize, W: usize, //M: [[u8; W]; H], M: [u8; W*H], } let mut uf = UnionFind::new(H*W); for y in 0..H { for x in 0..W { let idx = W*y + x; if x < W-1 && M[idx] == M[idx+1] { uf.unite(idx, idx+1); } if y < H-1 && M[idx] == M[idx+W] { uf.unite(idx, idx+W); } }} let mut ans = 0; for i in 0..H*W { if i == uf.v[i] && M[i] == 1 { ans += 1; } } println!("{}", ans); }