use proconio::input; use proconio::marker::Chars; struct UnionFind { uf: Vec, size: Vec, } impl UnionFind { fn new(n: usize) -> Self { UnionFind { uf: (0..n).collect(), size: vec![1; n], } } fn find(&mut self, x: usize) -> usize { if self.uf[x] == x { return x; } self.uf[x] = self.find(self.uf[x]); self.uf[x] } fn merge(&mut self, x: usize, y: usize) { let x = self.find(x); let y = self.find(y); if x == y { return; } if self.size[x] > self.size[y] { self.size[x] += self.size[y]; self.uf[y] = self.uf[x]; } else { self.size[y] += self.size[x]; self.uf[x] = self.uf[y]; } } fn size(&mut self, x: usize) -> usize { let x = self.find(x); self.size[x] } } fn main() { input! { h:usize, w:usize, g:[Chars;h], } let mut uf = UnionFind::new(h * w); for i in 0..h { for j in 0..w { if g[i][j] == '.' { continue; } if i + 1 < h && g[i][j] == g[i + 1][j] { uf.merge(i * w + j, (i + 1) * w + j); } if j + 1 < w && g[i][j] == g[i][j + 1] { uf.merge(i * w + j, i * w + j + 1); } } } for (i, tmp) in g.iter().enumerate() { for (j, item) in tmp.iter().enumerate() { if uf.size(i * w + j) >= 4 { print!("."); } else { print!("{}", item); } } println!(); } }