結果

問題 No.13 囲みたい！
コンテスト
ユーザー rpy3cpp
提出日時 2015-08-07 23:02:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 76 ms / 5,000 ms
コード長 3,077 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-10-13 10:46:50
合計ジャッジ時間 1,632 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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):
    '''連結したマスから、連結箇所が１つだけのマス（行き止まりのマス）を削除していく。
    行き止まりがなくなった時に、マスが残っているならば、そのマスは、閉路を構成しているはず。
    閉路は四角形以上になるはずだから、マスが残るかどうかを調べればよい。
    '''
    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