#P1609. 2023.09.28-JD-第二题-塔子哥的矩阵

2023.09.28-JD-第二题-塔子哥的矩阵

题目描述

塔子哥得到了一个矩阵。

该矩阵有若干个格子是黑色的，其余为白色，塔子哥希望将不多于 kk 个白色格子变成红色。特殊的，如果有两个红色格子纵向相邻，塔子哥会把上面的红色格子看作是“优美的”。

塔子哥想知道，最多可以有多少个优美的格子？

输入格式

第一行三个整数 n,m,kn,m,k，分别表示矩阵的行数和列数以及最多可以改变颜色的格子数。

接下来输入一个 n×mn \times m 的矩阵，表示矩阵的初始形态，其中 * 表示该格子为黑色，o 表示白色。

1≤n,m≤10001 \le n,m \le 1000

1≤k≤n×m1 \le k \le n \times m

输出格式

一个整数表示答案。

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

1

知识点:*****

查看知识点以及同类型题目

Statistics