結果

問題 No.640 76本のトロンボーン
ユーザー lam6er
提出日時 2025-03-31 18:02:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,705 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 67,688 KB
最終ジャッジ日時 2025-03-31 18:02:30
合計ジャッジ時間 1,558 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 8 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    grid = []
    for _ in range(N):
        grid.append(input[idx])
        idx +=1
    
    # Check for vertical possible (columns)
    vertical = []
    for j in range(N):
        column = [grid[i][j] for i in range(N)]
        consecutive = 0
        possible = False
        for c in column:
            if c == '.':
                consecutive +=1
                if consecutive >= N-1:
                    possible = True
                    break
            else:
                consecutive = 0
        if possible:
            vertical.append(j)
    v = len(vertical)
    
    # Check for horizontal possible (rows)
    horizontal = []
    for i in range(N):
        row = grid[i]
        consecutive = 0
        possible = False
        for c in row:
            if c == '.':
                consecutive +=1
                if consecutive >= N-1:
                    possible = True
                    break
            else:
                consecutive = 0
        if possible:
            horizontal.append(i)
    h = len(horizontal)
    
    # Build bipartite graph
    # Vertical on left (v nodes), horizontal on right (h nodes)
    # Create indices mapping
    vert_to_idx = {col: idx for idx, col in enumerate(vertical)}
    horz_to_idx = {row: idx for idx, row in enumerate(horizontal)}
    
    class BipartiteMatching:
        def __init__(self, n, m):
            self.n = n
            self.m = m
            self.graph = [[] for _ in range(n)]
            self.match_to = [-1] * m
            self.used = [False] * n

        def add_edge(self, u, v):
            self.graph[u].append(v)

        def dfs(self, v):
            self.used[v] = True
            for u in self.graph[v]:
                w = self.match_to[u]
                if w < 0 or (not self.used[w] and self.dfs(w)):
                    self.match_to[u] = v
                    return True
            return False

        def maximum_matching(self):
            res = 0
            for v in range(self.n):
                if self.used[v]:
                    continue
                self.used = [False] * self.n
                if self.dfs(v):
                    res += 1
            return res

    bm = BipartiteMatching(v, h)
    for vert_col in vertical:
        vidx = vert_to_idx[vert_col]
        for horz_row in horizontal:
            hidx = horz_to_idx[horz_row]
            if grid[horz_row][vert_col] == '.':
                bm.add_edge(vidx, hidx)
    
    max_matching = bm.maximum_matching()
    result = v + h - max_matching
    print(result)

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