結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:00:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,995 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,528 KB
実行使用メモリ 152,828 KB
最終ジャッジ日時 2025-06-12 16:00:46
合計ジャッジ時間 5,200 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1
    grid = []
    for _ in range(N):
        grid.append(input[idx])
        idx += 1
    
    visited = [[False for _ in range(M)] for _ in range(N)]
    loops = []
    directions = [(-1,-1), (-1,0), (-1,1),
                  (0,-1),         (0,1),
                  (1,-1),  (1,0), (1,1)]
    
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'x' and not visited[i][j]:
                loop = []
                stack = [(i, j, None)]
                while stack:
                    x, y, prev_dir = stack.pop()
                    if visited[x][y]:
                        continue
                    visited[x][y] = True
                    loop.append((x, y))
                    found = False
                    for dx, dy in directions:
                        nx = x + dx
                        ny = y + dy
                        if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] == 'x' and (nx, ny) != (i, j) and (nx, ny) not in loop:
                            stack.append((nx, ny, (dx, dy)))
                            found = True
                            break
                    if not found and len(loop) > 0:
                        break
                if len(loop) >= 3:
                    min_i = min(x for x, y in loop)
                    max_i = max(x for x, y in loop)
                    min_j = min(y for x, y in loop)
                    max_j = max(y for x, y in loop)
                    loops.append({'size': len(loop), 'mbr': (min_i, max_i, min_j, max_j)})
    
    parent = [None] * len(loops)
    for i in range(len(loops)):
        a_min_i, a_max_i, a_min_j, a_max_j = loops[i]['mbr']
        best_parent = None
        min_area = float('inf')
        for j in range(len(loops)):
            if i == j:
                continue
            b_min_i, b_max_i, b_min_j, b_max_j = loops[j]['mbr']
            if (b_min_i <= a_min_i and b_max_i >= a_max_i and
                b_min_j <= a_min_j and b_max_j >= a_max_j):
                area = (b_max_i - b_min_i + 1) * (b_max_j - b_min_j + 1)
                if area < min_area:
                    min_area = area
                    best_parent = j
        if best_parent is not None:
            parent[i] = best_parent
    
    children = [[] for _ in range(len(loops))]
    for i in range(len(loops)):
        if parent[i] is not None:
            children[parent[i]].append(i)
    
    def dfs(u):
        dp0 = 0
        dp1 = loops[u]['size']
        for v in children[u]:
            c0, c1 = dfs(v)
            dp0 += max(c0, c1)
            dp1 += c0
        return dp0, dp1
    
    total = 0
    for i in range(len(loops)):
        if parent[i] is None:
            c0, c1 = dfs(i)
            total += max(c0, c1)
    
    print(total)

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