题解 | 小红的矩阵染色

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m, k;
    cin>>n>>m>>k;
    vector<vector<char> > a (n + 1, vector<char> (m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>a[i][j];
    if(m == 1) {
        cout<<0;
        return 0;
    }
    int ans = 0;
    vector<int> b;
    for(int i = 1; i <= n; i++) {
        if(k <= 0) continue;
        for(int j = 1; j <= m; j++) {
            if(a[i][j] != 'o') continue;
            if(i == n) continue;
            if(a[i+1][j] != 'o') continue;
            int tmp = 0;
            for(int t = i; t <= n && a[t][j] == 'o'; t++) {
                a[t][j] = 'r';
                tmp ++;
            }
            b.push_back(tmp-1);
        }
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());
    for(int i:b) {
        ans += min(k - 1, i);
        k = max(0, k - i - 1);
        if(k == 0) break;
    }
    cout<<ans;
    return 0;
}