题解 | 小红的矩阵染色

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
    思路：
        先找出每列中 所有至少连续2个空白被染成红色的数量，保存到数组中
        再对每列的数量进行排序，筛选前 k 个
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        char[][] arr = new char[1001][1001]; // 矩阵
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            List<Integer> column = new ArrayList<>(); // 记录所有连续空白(至少2个) 的数量
            int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
            for (int i = 0; i < n; i++) {
                arr[i] = in.next().toCharArray();
            }
            // 按列查找
            for (int j = 0; j < m; j++) {
                int con_white = 0; // 记录连续的空白
                for (int i = 0; i < n; i++) {
                    if (arr[i][j] == 'o') {
                        con_white++;
                        if (i == n - 1 && con_white >= 2) {
                            column.add(con_white);
                        }
                    } else { // 遇到黑色，需要添加到column中，并置0
                        if (con_white >= 2) {
                            column.add(con_white);
                        }
                        con_white = 0;
                    }
                }
            }
		    // 按从大到小排序
            column.sort((num1, num2) -> num2 - num1);
            int score = 0, pos = 0;
            while (k > 0 && pos < column.size()) {
                if (column.get(pos) <= k) { // k 比较大
                    score += column.get(pos) - 1;
                    k -= column.get(pos);
                    pos++;
                } else if (column.get(pos) > k && k >= 2) {
                    score += k - 1;
                    k = 0;
                } else {
                    k = 0;
                }
            }
            System.out.println(score);
        }
    }
}