小红的矩阵染色

[编程题]小红的矩阵染色

热度指数：5594 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红拿到了一个矩阵，初始有一些格子被染成了黑色。现在小红希望把最多 $k$ 个未被染成黑色的格子染成红色，具体的计分方式是：如果一个红色格子下方相邻的格子也是红色，那么这个红色格子可以获得1分。
小红想知道，最多可以得到多少分？

输入描述:

第一行输入三个正整数，代表矩阵的行数和列数、以及小红最多可以染色的格子数量。
接下来的行，每行输入一个长度为的字符串，用来表示矩阵的初始染色情况。'*'字符代表黑色，'o'字符代表白色。

输出描述:

一个整数，代表小红可以获得的最大分数。

示例1

输入

4 4 3
*o*o
oooo
****
oooo

输出

说明

将矩阵染色成如下样式即可（'r'代表红色）：
*r*o
oroo
****
oooo

示例2

输入

3 3 3
*o*
*o*
*o*

输出

算法知识视频讲解

Python3

能干的勇士不放弃

import sys
a = [ i.replace('\n','') for i in list(sys.stdin)]
n,m,k = tuple(map(int,a[0].split(' ')))
a.pop(0)
max_o = []
score = 0
for j in range(m):
    count = 0
    for i in range(n):
        if a[i][j] == 'o':
            count += 1
        else:
            max_o.append(count)
            count = 0
            continue
    max_o.append(count)
max_o = sorted(max_o,reverse=True)
for j in range(len(max_o)):
    max_geze = max_o[j]
    if k==0&nbs***bsp;max_geze == 0:
        break
    if k > 0:
        if k > max_geze:
            score += max_geze-1
            k -= max_geze
        else:
            score += k-1
            k = 0
print(score)

发表于 2025-08-29 11:08:57 回复(0)