ABC450 C — Puddles

1# -*- coding: utf-8 -*-2 3from typing import List4 5 6class UnionFind:7    """Represents a data structure that tracks a set of elements partitioned8       into a number of disjoint (non-overlapping) subsets.9 10    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.11 12    See:13    https://www.youtube.com/watch?v=zV3Ul2pA2Fw14    https://en.wikipedia.org/wiki/Disjoint-set_data_structure15    https://atcoder.jp/contests/abc120/submissions/444494216    https://atcoder.jp/contests/abc292/submissions/3941007517    https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py18    """19 20    def __init__(self, number_count: int) -> None:21        """22        Args:23            number_count: The size of elements (greater than 2).24        """25        self.number_count = number_count26        self.parent_numbers = [-1 for _ in range(number_count)]27        self.edge_count = [0 for _ in range(number_count)]28        self.group_count = number_count29 30    def find_root(self, number: int) -> int:31        """Follows the chain of parent pointers from number up the tree until32           it reaches a root element, whose parent is itself.33        Args:34            number: The trees id (0-index).35 36        Returns:37            The index of a root element.38        """39        if self.parent_numbers[number] < 0:40            return number41 42        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])43        return self.parent_numbers[number]44 45    def get_group_size(self, number: int) -> int:46        """47        Args:48            number: The trees id (0-index).49 50        Returns:51            The size of group.52        """53        return -self.parent_numbers[self.find_root(number)]54 55    def is_same_group(self, number_x: int, number_y: int) -> bool:56        """Represents the roots of tree number_x and number_y are in the same57           group.58        Args:59            number_x: The trees x (0-index).60            number_y: The trees y (0-index).61        """62        return self.find_root(number_x) == self.find_root(number_y)63 64    def merge_if_needs(self, number_x: int, number_y: int) -> bool:65        """Uses find_root to determine the roots of the tree number_x and66           number_y belong to. If the roots are distinct, the trees are combined67           by attaching the roots of one to the root of the other.68        Args:69            number_x: The trees x (0-index).70            number_y: The trees y (0-index).71        """72        x = self.find_root(number_x)73        y = self.find_root(number_y)74 75        self.edge_count[x] += 176 77        if x == y:78            return False79 80        self.group_count -= 181 82        if self.parent_numbers[x] > self.parent_numbers[y]:83            x, y = y, x84 85        self.parent_numbers[x] += self.parent_numbers[y]86        self.parent_numbers[y] = x87        self.edge_count[x] += self.edge_count[y]88        return True89 90    def get_roots(self) -> List[int]:91        return [i for i, x in enumerate(self.parent_numbers) if x < 0]92 93    def get_groups(self) -> List[List[int]]:94        roots: List[int] = [self.find_root(i) for i in range(self.number_count)]95        groups: List[List[int]] = [[] for _ in range(self.number_count)]96 97        for i in range(self.number_count):98            groups[roots[i]].append(i)99 100        return list(filter(lambda g: g, groups))101 102    def get_edge_count(self, number: int) -> int:103        return self.edge_count[number]104 105    def get_group_count(self) -> int:106        return self.group_count107 108 109# See110# https://atcoder.jp/contests/abc450/submissions/74271594111def encode(hi, wj, w):112    return hi * w + wj113 114 115def decode(n, w):116    return divmod(n, w)117 118 119def main():120    import sys121 122    input = sys.stdin.readline123 124    h, w = map(int, input().split())125    s = [list(input().rstrip()) for _ in range(h)]126    uf = UnionFind(h * w)127 128    for i in range(h):129        ni = i + 1130 131        for j in range(w):132            if s[i][j] == "#":133                continue134 135            nj = j + 1136 137            if nj < w and s[i][nj] == ".":138                uf.merge_if_needs(encode(i, j, w), encode(i, nj, w))139            if ni < h and s[ni][j] == ".":140                uf.merge_if_needs(encode(i, j, w), encode(ni, j, w))141 142    all, ng = set(), set()143 144    for i in range(h):145        for j in range(w):146            if s[i][j] == "#":147                continue148 149            root = uf.find_root(encode(i, j, w))150            all.add(root)151 152            if i == 0 or j == 0 or i == h - 1 or j == w - 1:153                ng.add(root)154 155    ans = len(all) - len(ng)156    print(ans)157 158 159if __name__ == "__main__":160    main()161