結果

問題 No.861 ケーキカット
ユーザー gew1fw
提出日時 2025-06-12 16:54:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,193 bytes
コンパイル時間 487 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 64,640 KB
最終ジャッジ日時 2025-06-12 16:54:47
合計ジャッジ時間 2,551 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations
from collections import deque

def main():
    grid = []
    for _ in range(5):
        row = list(map(int, sys.stdin.readline().split()))
        grid.append(row)
    
    total = sum(sum(row) for row in grid)
    minimal_diff = float('inf')
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    connected_regions = []
    
    for i in range(5):
        for j in range(5):
            visited = set()
            q = deque()
            q.append((i, j))
            visited.add((i, j))
            regions = []
            while q:
                x, y = q.popleft()
                regions.append((x, y))
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < 5 and 0 <= ny < 5 and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        q.append((nx, ny))
            connected_regions.append(frozenset(regions))
    
    unique_regions = []
    seen = set()
    for region in connected_regions:
        if region not in seen:
            seen.add(region)
            unique_regions.append(region)
    
    for i in range(len(unique_regions)):
        a1 = unique_regions[i]
        sum_a1 = sum(grid[x][y] for x, y in a1)
        for j in range(i + 1, len(unique_regions)):
            a2 = unique_regions[j]
            if a1 & a2:
                continue
            sum_a2 = sum(grid[x][y] for x, y in a2)
            a_total = sum_a1 + sum_a2
            b_remaining = set()
            for x in range(5):
                for y in range(5):
                    if (x, y) not in a1 and (x, y) not in a2:
                        b_remaining.add((x, y))
            if len(b_remaining) < 2:
                continue
            
            q = deque()
            q.append((b_remaining.copy(), None))
            found = False
            while q:
                current, parent = q.popleft()
                if not current:
                    continue
                if parent is None:
                    x, y = next(iter(current))
                    child = current.copy()
                    child.remove((x, y))
                    q.append((child, frozenset([(x, y)])))
                else:
                    for cell in current:
                        x, y = cell
                        new_region = set(parent)
                        new_region.add((x, y))
                        new_region_frozen = frozenset(new_region)
                        if new_region not in seen:
                            seen.add(new_region_frozen)
                            unique_regions.append(new_region)
                        child = current.copy()
                        child.remove((x, y))
                        q.append((child, new_region_frozen))
            
            remaining_set = frozenset(b_remaining)
            if remaining_set not in seen:
                continue
            
            for region in unique_regions:
                if region.issubset(b_remaining):
                    b1 = region
                    b2 = b_remaining - b1
                    if len(b2) == 0 or not is_connected(b2):
                        continue
                    if is_connected(b1) and is_connected(b2):
                        found = True
                        break
            
            if found:
                b_total = total - a_total
                diff = abs(a_total - b_total)
                if diff < minimal_diff:
                    minimal_diff = diff
                if diff == 0:
                    print(0)
                    return
    
    print(minimal_diff)

def is_connected(region):
    if not region:
        return False
    start = next(iter(region))
    visited = set()
    q = deque([start])
    visited.add(start)
    while q:
        x, y = q.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            if (nx, ny) in region and (nx, ny) not in visited:
                visited.add((nx, ny))
                q.append((nx, ny))
    return len(visited) == len(region)

if __name__ == "__main__":
    main()
0