题解 | 小红的矩阵染色

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    while (line = await readline()) {
        let [n, m, k] = line.split(' ').map(Number);
        const mtx = [];
        for (let i = 0; i < n; i++) {
            mtx[i] = (await readline()).split('');
        }


        let list = [];
		// 统计每列中连续o序列大于1的长度
        for (let i = 0; i < m; i++) {
            let len = 0;
            for (let j = 0; j < n; j++) {
                if (mtx[j][i] === '*') {
                    if (j > 0 && mtx[j - 1][i] === 'o') {
                        if (len > 1) {
                            list.push(len);
                        }
                        len = 0;
                    }
                    continue;
                }
                len++;
            }
            if (len > 1) {
                list.push(len);
            }
        }

        list.sort((a, b) => b - a); // 从大到小排序

        let ans = 0;
        let i = 0;
        while (k > 0 && i < list.length) { // 遍历k，优先染色较长的序列
            if (list[i] > k) {
                ans += k-1;
                break;
            }
            k -= list[i];
            ans += list[i]-1;
            i++;
        }

        console.log(ans);
    }
}()