题解 | 小红的矩阵染色

import sys

def solve():
    input = sys.stdin.readline
    n, m, k = list(map(int, input().split()))
    grid = [list(input().strip()) for _ in range(n)]
    st = [[False] * m for _ in range(n)]

    def dfs(i, j):
        st[i][j] = True
        size = 1
        x, y = i + 1, j
        if 0 <= x < n and not st[x][y] and grid[x][y] == "o":
            size += dfs(x, y)
        return size
    
    sizes = []
    for i, row in enumerate(grid):
        for j, ch in enumerate(row):
            if ch == 'o' and not st[i][j]:
                size = dfs(i, j)
                sizes.append(size)
    res = 0
    sizes.sort(reverse=True)
    for size in sizes:
        if k >= size:
            k -= size
            res += size-1
        else:
            if k >= 2:
                res += k - 1
                k = 0
            break
    print(res)




solve()