結果

問題 No.697 池の数はいくつか
ユーザー neko_the_shadow
提出日時 2018-06-10 12:02:01
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 1,291 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 413 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 849,380 KB
最終ジャッジ日時 2024-11-25 13:10:08
合計ジャッジ時間 38,224 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 2 WA * 24 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import itertools, collections

class UnionFind(object):
    def __init__(self, h, w, field):
        self.parents = {(x, y) : () for x, y in itertools.product(range(h), range(w)) if field[x][y] == 1}

    def find(self, x, y):
        child = (x, y)
        while True:
            parent = self.parents[child]
            if parent:
                child = parent
            else:
                return child

    def union(self, x1, y1, x2, y2):
        parent1 = self.find(x1, y1)
        parent2 = self.find(x2, y2)
        if parent1 != parent2:
            self.parents[parent1] = parent2
    
    def count(self):
        count = 0
        for parent in self.parents.values():
            if not parent: count += 1
        return count

if __name__ == '__main__':
    h, w = map(int, input().split())
    field = tuple(tuple(map(int, input().split())) for _ in range(h))
    
    uf = UnionFind(h, w, field)
    diffs = ((1, 0), (0, 1))
    for x1, y1 in itertools.product(range(h), range(w)):
        if field[x1][y1] == 0:
            continue

        for dx, dy in diffs:
            x2, y2 = x1 + dx, y1 + dy
            print(x1, y1, x2, y2)
            if 0 <= x2 < h and 0 <= y2 < w and field[x2][y2] == 1:
                uf.union(x1, y1, x2, y2)
    
    print(uf.count())
0