結果

問題 No.348 カゴメカゴメ
ユーザー lam6er
提出日時 2025-04-15 23:53:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,980 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 122,648 KB
最終ジャッジ日時 2025-04-15 23:55:02
合計ジャッジ時間 5,299 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)

def main():
    N, M = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(N)]
    
    # Step 1: Extract cycles using BFS to trace the perimeter
    visited = [[False]*M for _ in range(N)]
    cycles = []
    
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'x' and not visited[i][j]:
                start = (i, j)
                current = start
                prev = None
                cycle = []
                while True:
                    cycle.append(current)
                    visited[current[0]][current[1]] = True
                    next_cells = []
                    for dx in (-1, 0, 1):
                        for dy in (-1, 0, 1):
                            if dx == 0 and dy == 0:
                                continue
                            nx = current[0] + dx
                            ny = current[1] + dy
                            if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] == 'x' and (nx, ny) != prev:
                                next_cells.append((nx, ny))
                    if not next_cells:
                        break
                    if len(next_cells) == 1:
                        next_cell = next_cells[0]
                    else:
                        next_cell = next_cells[0]
                    prev = current
                    current = next_cell
                    if current == start:
                        break
                cycles.append((cycle, len(cycle)))
    
    # Step 2: Build parent-child relationships
    K = len(cycles)
    parent = [-1] * K
    
    def is_inside(point, cycle_points):
        x, y = point
        crossings = 0
        n = len(cycle_points)
        for i in range(n):
            (x1, y1) = cycle_points[i]
            (x2, y2) = cycle_points[(i + 1) % n]
            if (y1 < y and y2 >= y) or (y2 < y and y1 >= y):
                x_intersect = (y - y1) * (x2 - x1) / (y2 - y1 + 1e-9) + x1
                if x <= x_intersect:
                    crossings += 1
        return crossings % 2 == 1
    
    for i in range(K):
        (cycle_i, size_i) = cycles[i]
        x, y = cycle_i[0]
        candidate_parents = []
        for j in range(K):
            if i == j:
                continue
            (cycle_j, size_j) = cycles[j]
            if is_inside((x, y), cycle_j):
                candidate_parents.append(j)
        # Find the deepest parent (the one with the most nested)
        max_depth = -1
        selected_parent = -1
        for j in candidate_parents:
            current_depth = 0
            current = j
            while parent[current] != -1:
                current = parent[current]
                current_depth += 1
            if current_depth > max_depth:
                max_depth = current_depth
                selected_parent = j
        if candidate_parents:
            parent[i] = selected_parent
    
    # Step 3: Build tree and perform DP
    children = defaultdict(list)
    for i in range(K):
        if parent[i] != -1:
            children[parent[i]].append(i)
        else:
            children[-1].append(i)
    
    memo = {}
    def dp(u, can_use):
        if (u, can_use) in memo:
            return memo[(u, can_use)]
        res = 0
        if can_use:
            use_val = cycles[u][1]
            for v in children[u]:
                use_val += dp(v, False)
            not_use_val = 0
            for v in children[u]:
                not_use_val += dp(v, True)
            res = max(use_val, not_use_val)
        else:
            not_use_val = 0
            for v in children[u]:
                not_use_val += dp(v, True)
            res = not_use_val
        memo[(u, can_use)] = res
        return res
    
    total = 0
    for root in children[-1]:
        total += dp(root, True)
    print(total)

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