题解 | 小红的矩阵染色

void solve(){
    int n, m, k;
    cin >> n >> m >> k; 
    vector<vector<char>> a(n, vector<char>(m));
    // 读入矩阵
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            a[i][j] = s[j];
        }
    }
    vector<int> p; // 存每一列中连续白色格子的长度
    // 因为得分只看“下方相邻格子是否也是红色”
    // 所以只需要按列来统计连续的白色格子段
    for(int i = 0; i < m; i++){ // 枚举每一列
        int res = 0; // 当前连续白色格子的数量
        for(int j = 0; j < n; j++){ // 从上到下扫这一列
            if(a[j][i] == 'o'){
                res++; // 遇到白色格子，连续长度加1
            }
            else if(a[j][i] != 'o' && res){
                // 遇到黑色格子，说明前面一段连续白格结束了
                p.push_back(res); // 把这一段长度存下来
                res = 0;          // 重新开始统计
            }
        }
        // 如果这一列最后也是白色格子，循环结束后还要把最后一段加入
        if(res){
            p.push_back(res);
            res = 0;
        }
    }
    // 优先选择长度更长的连续白格段
    // 因为一段长度为x的连续红格，最多可以贡献 x - 1 分
    sort(p.begin(), p.end(), greater<int>());
    int ans = 0; // 最终最大得分
    for(int i = 0; i < p.size(); i++){
        if(k <= 0) break; // 没有可染色的格子了，直接结束
        if(k >= p[i]){
            // 如果剩余染色次数足够染完整段
            k -= p[i];        // 用掉p[i]个染色次数
            ans += p[i] - 1;  // 连续p[i]个红格可以获得p[i]-1分
        }
        else{
            // 如果不能染完整段，只能染k个格子
            // 连续染k个格子，可以获得k-1分
            ans += k - 1;
            k = 0;
        }
    }
    cout << ans << endl;
}