結果

問題 No.348 カゴメカゴメ
ユーザー lam6er
提出日時 2025-03-31 17:52:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,118 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 82,852 KB
実行使用メモリ 278,592 KB
最終ジャッジ日時 2025-03-31 17:53:25
合計ジャッジ時間 7,065 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 1 TLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]
    
    visited = [[False for _ in range(m)] for __ in range(n)]
    dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    adj = {}
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] != 'x':
                continue
            neighbors = []
            for dx, dy in dirs:
                ni, nj = i + dx, j + dy
                if 0 <= ni < n and 0 <= nj < m and grid[ni][nj] == 'x':
                    neighbors.append((ni, nj))
            adj[(i, j)] = neighbors
    
    cycles = []
    visited = [[False]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'x' and not visited[i][j]:
                component = []
                q = deque([(i, j)])
                visited[i][j] = True
                while q:
                    x, y = q.popleft()
                    component.append((x, y))
                    for nx, ny in adj[(x, y)]:
                        if not visited[nx][ny]:
                            visited[nx][ny] = True
                            q.append((nx, ny))
                
                start = component[0]
                ordered = []
                current = start
                prev = None
                while True:
                    ordered.append(current)
                    neighbors = adj[current]
                    next_node = None
                    for n in neighbors:
                        if n in component and n != prev:
                            next_node = n
                            break
                    if next_node is None:
                        break
                    if next_node == ordered[0] and len(ordered) > 1:
                        break
                    prev = current
                    current = next_node
                if len(ordered) >= 3:
                    cycles.append(ordered)
    
    class CycleInfo:
        def __init__(self, points):
            self.points = points
            self.size = len(points)
            min_x = min(p[0] for p in points)
            min_y = min(p[1] for p in points)
            self.rep_point = (min_x, min_y)
            self.mbr = (min(p[0] for p in points), min(p[1] for p in points),
                        max(p[0] for p in points), max(p[1] for p in points))
            self.polygon = [(x + 0.5, y + 0.5) for x, y in points]
            self.children = []
            self.parent = None

    cycle_infos = [CycleInfo(cycle) for cycle in cycles]
    cycle_infos.sort(key=lambda ci: -((ci.mbr[2]-ci.mbr[0]+1) * (ci.mbr[3]-ci.mbr[1]+1)))
    
    def point_in_mbr(point, mbr):
        x, y = point
        return mbr[0] <= x <= mbr[2] and mbr[1] <= y <= mbr[3]
    
    def is_point_inside_polygon(point, polygon):
        px, py = point
        crossings = 0
        n = len(polygon)
        for i in range(n):
            x1, y1 = polygon[i]
            x2, y2 = polygon[(i+1)%n]
            if (y1 < py and y2 >= py) or (y2 < py and y1 >= py):
                if y1 == y2:
                    continue
                x_intersect = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
                if px <= x_intersect:
                    crossings += 1
        return crossings % 2 == 1
    
    roots = []
    for ci in cycle_infos:
        rx, ry = ci.rep_point
        p = (rx + 0.5, ry + 0.5)
        candidate_parent = None
        for ancestor in reversed(cycle_infos):
            if ancestor == ci:
                continue
            if not point_in_mbr(ci.rep_point, ancestor.mbr):
                continue
            apoly = ancestor.polygon
            if is_point_inside_polygon(p, apoly):
                current = ancestor
                found = None
                stack = [(current, current.children)]
                while stack:
                    node, children = stack.pop()
                    for child in children:
                        if point_in_mbr(ci.rep_point, child.mbr) and is_point_inside_polygon(p, child.polygon):
                            stack.append((child, child.children))
                            current = child
                candidate_parent = current
                break
        if candidate_parent is not None:
            candidate_parent.children.append(ci)
            ci.parent = candidate_parent
        else:
            roots.append(ci)
    
    memo = {}
    def dp(node):
        if node in memo:
            return memo[node]
        use = node.size
        for child in node.children:
            res = dp(child)
            use += res[1]
        not_use = 0
        for child in node.children:
            res = dp(child)
            not_use += max(res[0], res[1])
        memo[node] = (use, not_use)
        return (use, not_use)
    
    max_sum = 0
    for root in roots:
        u, nu = dp(root)
        max_sum += max(u, nu)
    print(max_sum)

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