首页 > 试题广场 >

小红的矩阵染色

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

热度指数：3736 时间限制：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}$ 请你帮小红计算，经过最优染色后，最多能获得多少分数。

输入描述:

第一行输入三个整数 ，分别表示矩阵行数、列数及最多可染红的格子数量。
此后  行，每行输入一个长度为  的字符串 ，描述第  行初始状态：
 ```` 代表黑色格子，不能重新染色；
 ```` 代表空白格子，可选择染为红色。

输出描述:

输出一个整数，表示小红通过最佳策略能够获得的最大分数。

示例1

输入

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

输出

说明

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

*r*o
oroo
****
oooo

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

示例2

输入

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

输出

算法知识视频讲解

Python3

牛客341639822号

n, m, k = map(int, input().split())
array = [[x for x in input()] for _ in range(n)]
arr = [] # 记录每个连续空白可得分数 for col in range(m):
    coun = -1  for row in range(n): # 遇到黑色格子，存储分数，并重置  if array[row][col] == '*': if coun >= 0: # 避免连续黑色格子添加-1的情况  arr.append(coun)
            coun = -1  else:
            coun += 1  # 列尾时添加该分数到arr  if coun >= 0:
        arr.append(coun)
arr.sort(reverse=True)
score = 0 for i in range(len(arr)): if arr[i]+1 < k:
        score += arr[i]
        k -= (arr[i]+1) else:
        score += (k-1)
        k = 0  break print(score)

发表于 2025-10-04 18:36:18 回复(0)

Python3

牛客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)

提交观点

问题信息

贪心

难度：

2条回答 33收藏 638浏览

小红的矩阵染色

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题