题解 | 小红的矩阵染色

import sys

# 读取输入（处理大规模输入更高效）
input_lines = sys.stdin.read().splitlines()
n, m, k = map(int, input_lines[0].split())
grid = input_lines[1:n+1]  # 后续n行为矩阵内容

# 存储所有纵向连续'o'的长度（仅收集有效长度，后续用于计算得分）
vertical_continuous_lengths = []

# 遍历每一列（纵向统计，核心：按列遍历更直观统计纵向连续）
for j in range(m):
    current_continuous = 0  # 记录当前列的纵向连续'o'长度
    for i in range(n):
        if grid[i][j] == 'o':
            current_continuous += 1
            # 仅当到达列尾或下一个不是'o'时，收集连续长度（避免重复收集）
            if i == n-1 or grid[i+1][j] != 'o':
                if current_continuous >= 1:  # 至少1个才有效，≥2才有得分价值（后续会自动过滤）
                    vertical_continuous_lengths.append(current_continuous)
                current_continuous = 0
        else:
            # 遇到'*'，中断连续，重置计数
                current_continuous = 0

# 核心步骤：降序排序，优先选择最长的连续段（最大化得分效率）
vertical_continuous_lengths.sort(reverse=True)

total_score = 0  # 记录总分
remaining_k = k  # 剩余可染色格子数，避免修改原始k

# 遍历排序后的连续段，累计最大得分
for length in vertical_continuous_lengths:
    if remaining_k <= 1:#1个无法得分
        break  # 无剩余染色名额，终止循环
    if remaining_k>=2:
        total_score+=min(length,remaining_k)-1 #比较剩余涂色数，和o长度，选择小的-1
        remaining_k-=min(length,remaining_k)   #修改剩余涂色数

print(total_score)