結果

問題 No.13 囲みたい!
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-07 23:02:51
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 58 ms / 5,000 ms
コード長 3,077 bytes
コンパイル時間 632 ms
コンパイル使用メモリ 11,240 KB
実行使用メモリ 13,844 KB
最終ジャッジ日時 2023-08-03 13:56:42
合計ジャッジ時間 1,363 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
8,872 KB
testcase_01 AC 19 ms
8,840 KB
testcase_02 AC 19 ms
8,824 KB
testcase_03 AC 39 ms
12,200 KB
testcase_04 AC 58 ms
13,844 KB
testcase_05 AC 46 ms
12,020 KB
testcase_06 AC 33 ms
10,820 KB
testcase_07 AC 36 ms
11,068 KB
testcase_08 AC 31 ms
11,428 KB
testcase_09 AC 31 ms
11,236 KB
testcase_10 AC 21 ms
9,228 KB
testcase_11 AC 31 ms
10,916 KB
testcase_12 AC 20 ms
8,920 KB
testcase_13 AC 23 ms
9,672 KB
testcase_14 AC 23 ms
9,756 KB
testcase_15 AC 19 ms
8,852 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import collections


class DisjointSet(object):
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.num = n  # number of disjoint sets

    def union(self, x, y):
        self._link(self.find_set(x), self.find_set(y))

    def _link(self, x, y):
        if x == y:
            return
        self.num -= 1
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def find_set(self, x):
        xp = self.parent[x]
        if xp != x:
            self.parent[x] = self.find_set(xp)
        return self.parent[x]


def read_data():
    W, H = map(int, input().split())
    data = [[0] * (W + 1)]
    for h in range(H):
        row = list(map(int, input().split()))
        data.append([0] + row + [0])
    data.append([0] * (W + 1))
    return W, H, data

def solve(W, H, data):
    groups = make_groups(data, W, H)
    for group in groups.values():
        if len(group) < 4:
            continue
        if has_kakoi(group, data):
            return True
    return False

def make_groups(data, W, H):
    djs = DisjointSet(W * H)
    idx = 0
    for h, row in enumerate(data[1:-1], 1):
        for w, color in enumerate(row[1:-1], 1):
            if color == data[h][w + 1]:
                djs.union(idx, idx + 1)
            if color == data[h + 1][w]:
                djs.union(idx, idx + W)
            idx += 1
    groups = collections.defaultdict(list)
    idx = 0
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            groups[djs.find_set(idx)].append((h, w))
            idx += 1
    return groups


def has_kakoi(group, data):
    '''連結したマスから、連結箇所が1つだけのマス(行き止まりのマス)を削除していく。
    行き止まりがなくなった時に、マスが残っているならば、そのマスは、閉路を構成しているはず。
    閉路は四角形以上になるはずだから、マスが残るかどうかを調べればよい。
    '''
    h, w = group[0]
    color = data[h][w]
    degrees, degree1 = count_degrees(group, data, color)
    while degree1:
        h, w = degree1[-1]
        nh, nw = degrees[h, w][0]
        degrees[h, w] = []
        del degree1[-1]
        degrees[nh, nw].remove((h, w))
        if len(degrees[nh, nw]) == 1:
            degree1.append((nh, nw))
        if len(degrees[nh, nw]) == 0:
            return False
    return True

def count_degrees(group, data, color):
    degrees = dict()
    degree1 = []
    for h, w in group:
        degrees[h, w] = []
        for nh, nw in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
            if data[nh][nw] == color:
                degrees[h, w].append((nh, nw))
        if len(degrees[h, w]) == 1:
            degree1.append((h, w))
    return degrees, degree1

if __name__ == '__main__':
    W, H, data = read_data()
    if solve(W, H, data):
        print('possible')
    else:
        print('impossible')
0