結果

問題 No.421 しろくろチョコレート
ユーザー lam6er
提出日時 2025-03-20 21:15:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,124 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 78,468 KB
最終ジャッジ日時 2025-03-20 21:15:54
合計ジャッジ時間 6,500 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 64 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

class HopcroftKarp:
    def __init__(self, graph, U, V):
        self.graph = graph  # adjacency list for left nodes (U)
        self.U = U
        self.V = V
        self.pair_u = [-1] * U  # pair for left nodes
        self.pair_v = [-1] * V  # pair for right nodes
        self.dist = [0] * U     # distance for BFS

    def bfs(self):
        queue = deque()
        for u in range(self.U):
            if self.pair_u[u] == -1:
                self.dist[u] = 0
                queue.append(u)
            else:
                self.dist[u] = float('inf')
        self.dist_null = float('inf')
        while queue:
            u = queue.popleft()
            if self.dist[u] < self.dist_null:
                for v in self.graph[u]:
                    if self.pair_v[v] == -1:
                        self.dist_null = self.dist[u] + 1
                    elif self.dist[self.pair_v[v]] == float('inf'):
                        self.dist[self.pair_v[v]] = self.dist[u] + 1
                        queue.append(self.pair_v[v])
        return self.dist_null != float('inf')

    def dfs(self, u):
        if u != -1:
            for v in self.graph[u]:
                if self.pair_v[v] == -1 or (self.dist[self.pair_v[v]] == self.dist[u] + 1 and self.dfs(self.pair_v[v])):
                    self.pair_u[u] = v
                    self.pair_v[v] = u
                    return True
            self.dist[u] = float('inf')
            return False
        return True

    def max_matching(self):
        result = 0
        while self.bfs():
            for u in range(self.U):
                if self.pair_u[u] == -1:
                    if self.dfs(u):
                        result += 1
        return result

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].strip())
        idx += 1

    w_positions = []
    b_positions = []
    for i in range(N):
        for j in range(M):
            c = grid[i][j]
            if c == 'w':
                w_positions.append((i, j))
            elif c == 'b':
                b_positions.append((i, j))

    U = len(w_positions)
    V = len(b_positions)
    if U == 0 or V == 0:
        print(0)
        return

    graph = [[] for _ in range(U)]
    b_map = {(i, j): idx for idx, (i, j) in enumerate(b_positions)}
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for u in range(U):
        i, j = w_positions[u]
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M:
                if grid[ni][nj] == 'b' and (ni, nj) in b_map:
                    v = b_map[(ni, nj)]
                    graph[u].append(v)

    hk = HopcroftKarp(graph, U, V)
    k = hk.max_matching()
    total_w = U
    total_b = V
    remaining_w = total_w - k
    remaining_b = total_b - k
    m = min(remaining_w, remaining_b)
    score = 100 * k + 10 * m + (remaining_w + remaining_b - 2 * m)
    print(score)

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