首页 > 试题广场 >

小红的矩阵染色

[编程题]小红的矩阵染色
  • 热度指数：1392 时间限制：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
算法知识视频讲解
添加回答
Python 3
忧伤的双曲线头像 忧伤的双曲线
n,m,k = map(int,input().split())
matrix = []
for i in range(n):
    matrix.append(input())

matrix_lie = list(zip(*matrix))
lis_o = []
for i in range(m):
    tmp = ''
    for j in range(n):
        if matrix_lie[i][j]=='o':
            tmp += 'o'
            if j==(n-1) and len(tmp)>=2:
                lis_o.append(tmp)
        else:
            if len(tmp)>=2:
                lis_o.append(tmp)
            tmp = ''
lis_o_sorted = sorted(lis_o,key=lambda x:-len(x))
score = 0
left = k
for item in lis_o_sorted:
    len_item = len(item)
    if left>=len_item:
        score += len_item-1
        left -= len_item
    elif 0<left<len_item:
        score += left-1
        left = 0
    elif left==0:
        break

print(score)
发表于 今天 01:39:39 回复(0)
提交观点

问题信息

贪心 排序
难度：
1条回答 100浏览

热门推荐

相关试题

小红的矩阵染色

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号