首页 > 试题广场 >

小红的矩阵染色

[编程题]小红的矩阵染色
  • 热度指数: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}请你帮小红计算,经过最优染色后,最多能获得多少分数。

输入描述:
\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

这道题你会答吗?花几分钟告诉大家答案吧!