結果

問題 No.640 76本のトロンボーン
ユーザー gew1fw
提出日時 2025-06-12 18:57:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,709 bytes
コンパイル時間 295 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 68,712 KB
最終ジャッジ日時 2025-06-12 18:57:11
合計ジャッジ時間 1,686 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    grid = [sys.stdin.readline().strip() for _ in range(N)]
    K = N - 1

    possible_rows = []
    row_coverage = []
    for i in range(N):
        left = True
        for j in range(K):
            if grid[i][j] == '#':
                left = False
                break
        right = True
        for j in range(1, N):
            if grid[i][j] == '#':
                right = False
                break
        if not left and not right:
            continue
        possible_rows.append(i)
        coverage = set()
        if left and right:
            for j in range(1, K):
                coverage.add(j)
        elif left:
            for j in range(K):
                coverage.add(j)
        else:
            for j in range(1, N):
                coverage.add(j)
        row_coverage.append(coverage)

    possible_cols = []
    col_coverage = []
    for j in range(N):
        top = True
        for i in range(K):
            if grid[i][j] == '#':
                top = False
                break
        bottom = True
        for i in range(1, N):
            if grid[i][j] == '#':
                bottom = False
                break
        if not top and not bottom:
            continue
        possible_cols.append(j)
        coverage = set()
        if top and bottom:
            for i in range(1, K):
                coverage.add(i)
        elif top:
            for i in range(K):
                coverage.add(i)
        else:
            for i in range(1, N):
                coverage.add(i)
        col_coverage.append(coverage)

    edges = [[] for _ in range(len(possible_rows))]
    row_id = {r: idx for idx, r in enumerate(possible_rows)}
    col_id = {c: idx for idx, c in enumerate(possible_cols)}

    for r_idx, r in enumerate(possible_rows):
        row_cov = row_coverage[r_idx]
        for c_idx, c in enumerate(possible_cols):
            col_cov = col_coverage[c_idx]
            if r in col_cov and c in row_cov:
                edges[r_idx].append(c_idx)

    def hopcroft_karp():
        pair_U = [-1] * len(possible_rows)
        pair_V = [-1] * len(possible_cols)
        dist = [0] * len(possible_rows)

        def bfs():
            queue = deque()
            for u in range(len(possible_rows)):
                if pair_U[u] == -1:
                    dist[u] = 0
                    queue.append(u)
                else:
                    dist[u] = float('inf')
            dist_null = float('inf')
            while queue:
                u = queue.popleft()
                if dist[u] < dist_null:
                    for v in edges[u]:
                        if pair_V[v] == -1:
                            dist_null = dist[u] + 1
                        elif dist[pair_V[v]] == float('inf'):
                            dist[pair_V[v]] = dist[u] + 1
                            queue.append(pair_V[v])
            return dist_null != float('inf')

        def dfs(u):
            for v in edges[u]:
                if pair_V[v] == -1 or (dist[pair_V[v]] == dist[u] + 1 and dfs(pair_V[v])):
                    pair_U[u] = v
                    pair_V[v] = u
                    return True
            dist[u] = float('inf')
            return False

        result = 0
        while bfs():
            for u in range(len(possible_rows)):
                if pair_U[u] == -1:
                    if dfs(u):
                        result += 1
        return result

    max_matching = hopcroft_karp()
    answer = len(possible_rows) + len(possible_cols) - max_matching
    print(answer)

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