結果

問題 No.697 池の数はいくつか
ユーザー neko_the_shadowneko_the_shadow
提出日時 2018-06-10 12:02:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,291 bytes
コンパイル時間 592 ms
コンパイル使用メモリ 86,672 KB
実行使用メモリ 818,592 KB
最終ジャッジ日時 2023-08-16 22:17:34
合計ジャッジ時間 17,004 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 92 ms
71,676 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 91 ms
71,340 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 MLE -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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