ABC325 C — Sensors

1# -*- coding: utf-8 -*-2 3 4from typing import List5 6 7class UnionFind:8    """Represents a data structure that tracks a set of elements partitioned9       into a number of disjoint (non-overlapping) subsets.10 11    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.12 13    See:14    https://www.youtube.com/watch?v=zV3Ul2pA2Fw15    https://en.wikipedia.org/wiki/Disjoint-set_data_structure16    https://atcoder.jp/contests/abc120/submissions/444494217    https://atcoder.jp/contests/abc292/submissions/3941007518    """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.parent_numbers = [-1 for _ in range(number_count)]26        self.edge_count = [0 for _ in range(number_count)]27        self.group_count = number_count28 29    def find_root(self, number: int) -> int:30        """Follows the chain of parent pointers from number up the tree until31           it reaches a root element, whose parent is itself.32        Args:33            number: The trees id (0-index).34 35        Returns:36            The index of a root element.37        """38        if self.parent_numbers[number] < 0:39            return number40 41        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])42        return self.parent_numbers[number]43 44    def get_group_size(self, number: int) -> int:45        """46        Args:47            number: The trees id (0-index).48 49        Returns:50            The size of group.51        """52        return -self.parent_numbers[self.find_root(number)]53 54    def is_same_group(self, number_x: int, number_y: int) -> bool:55        """Represents the roots of tree number_x and number_y are in the same56           group.57        Args:58            number_x: The trees x (0-index).59            number_y: The trees y (0-index).60        """61        return self.find_root(number_x) == self.find_root(number_y)62 63    def merge_if_needs(self, number_x: int, number_y: int) -> bool:64        """Uses find_root to determine the roots of the tree number_x and65           number_y belong to. If the roots are distinct, the trees are combined66           by attaching the roots of one to the root of the other.67        Args:68            number_x: The trees x (0-index).69            number_y: The trees y (0-index).70        """71        x = self.find_root(number_x)72        y = self.find_root(number_y)73 74        self.edge_count[x] += 175 76        if x == y:77            return False78 79        self.group_count -= 180 81        if self.parent_numbers[x] > self.parent_numbers[y]:82            x, y = y, x83 84        self.parent_numbers[x] += self.parent_numbers[y]85        self.parent_numbers[y] = x86        self.edge_count[x] += self.edge_count[y]87        return True88 89    def get_roots(self) -> List[int]:90        return [i for i, x in enumerate(self.parent_numbers) if x < 0]91 92    def get_edge_count(self, number: int) -> int:93        return self.edge_count[number]94 95    def get_group_count(self) -> int:96        return self.group_count97 98 99class UnionFind2D:100    """Extends UnionFind to two dimensions.101 102    See:103    https://atcoder.jp/contests/past202010-open/submissions/21472171104    """105 106    def __init__(self, height: int, width: int) -> None:107        self.height: int = height108        self.width: int = width109        self.size: int = height * width110        self.uf: UnionFind = UnionFind(self.size)111 112    def find_root(self, x: int, y: int) -> int:113        assert 0 <= x < self.width114        assert 0 <= y < self.height115 116        return self.uf.find_root(self._to_number(x, y))117 118    def get_group_size(self, x: int, y: int) -> int:119        assert 0 <= x < self.width120        assert 0 <= y < self.height121 122        return self.uf.get_group_size(self._to_number(x, y))123 124    def is_same_group(self, x1: int, y1: int, x2: int, y2: int) -> bool:125        assert 0 <= x1 < self.width126        assert 0 <= y1 < self.height127        assert 0 <= x2 < self.width128        assert 0 <= y2 < self.height129 130        return self.find_root(x1, y1) == self.find_root(x2, y2)131 132    def merge_if_needs(self, x1: int, y1: int, x2: int, y2: int) -> bool:133        assert 0 <= x1 < self.width134        assert 0 <= y1 < self.height135        assert 0 <= x2 < self.width136        assert 0 <= y2 < self.height137 138        return self.uf.merge_if_needs(self._to_number(x1, y1), self._to_number(x2, y2))139 140    def get_roots(self) -> List[int]:141        return self.uf.get_roots()142 143    def get_edge_count(self, x: int, y: int) -> int:144        assert 0 <= x < self.width145        assert 0 <= y < self.height146 147        return self.uf.get_edge_count(self._to_number(x, y))148 149    def get_group_count(self) -> int:150        return self.uf.get_group_count()151 152    def _to_number(self, x: int, y: int) -> int:153        """154        Args:155            x, y: Coordinates in grid (0-index).156 157        Returns:158            The trees id (0-index).159        """160        return x + self.width * y161 162 163def main():164    import sys165 166    input = sys.stdin.readline167 168    h, w = map(int, input().split())169    s = [list(input().rstrip()) for _ in range(h)]170    uf = UnionFind2D(height=h, width=w)171    dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]172 173    for i in range(h):174        for j in range(w):175            if s[i][j] == ".":176                continue177 178            for dx, dy in dxy:179                nx = j + dx180                ny = i + dy181 182                if not (0 <= nx < w):183                    continue184                if not (0 <= ny < h):185                    continue186                if s[ny][nx] == ".":187                    continue188 189                uf.merge_if_needs(j, i, nx, ny)190 191    ans = set()192 193    for i in range(h):194        for j in range(w):195            if s[i][j] == ".":196                continue197 198            ans.add(uf.find_root(j, i))199 200    print(len(ans))201 202 203if __name__ == "__main__":204    main()205