首页 > 试题广场 >

小红的矩阵染色

[编程题]小红的矩阵染色
  • 热度指数：1058 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个 n\times m 的矩阵，初始时部分格子已被染成黑色（用 ``\texttt{*}`` 表示），其余格子为空白（用 ``\texttt{o}`` 表示）。

\hspace{15pt}小红最多可以任选至多 k 个空白格子，将其染成红色。计分规则如下：
\hspace{23pt}\bullet\, 若某个红色格子的正下方（同一列下一行）也是红色，则该格子贡献 1 分；
\hspace{23pt}\bullet\, 其他情况不计分。

\hspace{15pt}请你帮小红计算，经过最优染色后，最多能获得多少分数。

输入描述:
\hspace{15pt}第一行输入三个整数 n,m,k\left(1\leqq n,m\leqq 10^3;\ 1\leqq k\leqq n\times m\right)，分别表示矩阵行数、列数及最多可染红的格子数量。
\hspace{15pt}此后 n 行，每行输入一个长度为 m 的字符串 s_i，描述第 i 行初始状态：
\hspace{23pt}\bullet\, ``\texttt{*}`` 代表黑色格子，不能重新染色；
\hspace{23pt}\bullet\, ``\texttt{o}`` 代表空白格子，可选择染为红色。


输出描述:
\hspace{15pt}输出一个整数，表示小红通过最佳策略能够获得的最大分数。
示例1

输入

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

输出

1

说明

一种可行方案如下（``\texttt{r}`` 为染成红色后的格子）：

\hspace{15pt}*r*o
\hspace{15pt}oroo
\hspace{15pt}****
\hspace{15pt}oooo

红色格子共有 2 个，其中正下方同列的红色对数为 1，因此得分 1。
示例2

输入

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

输出

2
算法知识视频讲解
添加回答
Python3
牛客847294653号头像 牛客847294653号
n, m, k = map(int, input().split())
s = [list(input()) for _ in range(n)]
whitecol = []

for j in range(m):
    numwhite = 0
    for i in range(n):
        if s[i][j] == 'o':
            numwhite += 1
        else:
            if numwhite > 1:
                whitecol.append(numwhite)
            numwhite = 0
    # 处理列末尾的连续空白
    if numwhite > 1:
        whitecol.append(numwhite)

whitecol.sort(reverse=True)
score = 0
leftred = k

for x in whitecol:
    if leftred >= x:
        score += x - 1  # 连续x个空白染红可以得到x-1分
        leftred -= x
    elif leftred > 1:  # 如果剩余可染红格子数大于1，仍然可以得分
        score += leftred - 1
        leftred = 0
        break

print(score)

发表于 2025-08-25 15:16:53 回复(0)
提交观点

问题信息

贪心
难度：
1条回答 39浏览

热门推荐

相关试题

小红的矩阵染色

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号