首页 > 试题广场 >

小红的矩阵染色

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

热度指数：1105 时间限制：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*

输出

算法知识视频讲解

手有余湘

发表于 2025-08-04 12:09:10

n,m,k=list(map(int,input().split())) black_longth=[] array=[i for i in input()] number=[1 if i=='o' else 0 for i in array] for _ in range(n-1):#竖向找出连续展开全文

小y虫-周伯通

发表于 2025-06-25 10:45:02

/* 先找出纵向连续白色格子最多的地方，然后得分就是纵向填充红色格子数-1，比如有纵向有5个白色格子，那得分就是5-1，直到用完k次数为止 */ import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 packag 展开全文

深藏功与名的懒羊羊很贴心

发表于 2025-07-09 09:30:51

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, m, k; cin >> n &g 展开全文

Silencer76

发表于 2025-08-09 16:50:17

题目链接小红的矩阵染色题目描述给定一个的矩阵，其中部分格子是黑色的（*），部分是空白的（o）。小红最多可以选择个空白格子，将它们染成红色。计分规则：如果一个红色格子的正下方也是红色，则这对相邻的红色格子贡献1分。求小红能获得的最大分数。解题思路本题要求在有限的染色次数（）下，展开全文

饥饿的中国人offer多多

发表于 2025-08-21 01:07:07

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = new S 展开全文

问题信息

贪心

难度：

1条回答 7收藏 54浏览

小红的矩阵染色

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题