首页 > 试题广场 >

小红的矩阵染色

[编程题]小红的矩阵染色
  • 热度指数:5594 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小红拿到了一个矩阵,初始有一些格子被染成了黑色。现在小红希望把最多k个未被染成黑色的格子染成红色,具体的计分方式是:如果一个红色格子下方相邻的格子也是红色,那么这个红色格子可以获得1分。
小红想知道,最多可以得到多少分?

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


输出描述:
一个整数,代表小红可以获得的最大分数。
示例1

输入

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

输出

1

说明

将矩阵染色成如下样式即可('r'代表红色):
*r*o
oroo
****
oooo

示例2

输入

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

输出

2

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