题解 | 小红的矩阵染色

#include <stdio.h>
#include <stdlib.h>

int compare(const void*a, const void*b){
    return(*(int*)b - *(int*)a);
}

int main(void) {
    int n, m, k;    //行 列 可染数
    scanf("%d%d%d", &n, &m, &k);

    char** ch = (char**)malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        ch[i] = (char*)malloc(m * sizeof(char));
    }

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf(" %c", &ch[i][j]);

    int*a = (int*)malloc(n*m* sizeof(int*));
    int size = 0;
    for(int j = 0; j < m; j++){
        for(int i = 0; i < n; i++){
            int s = 0;
            while(i < n && ch[i][j] == 'o'){
                s++;
                i++;
            }
            if(s-1>0)
                a[size++] = s-1;
        }
    }
    qsort(a, size, sizeof(int), compare);

    int ans = 0;
    for(int i = 0; i < size; i++){
        if(k >= a[i] + 1){
            ans += a[i];
            k -= a[i] + 1;
        }
        else if(k > 0){
            ans += k - 1;
            break;
        }
    }
    printf("%d\n", ans);

    for(int i = 0; i < n; i++)
        free(ch[i]);

    free(a);
    free(ch);
    return 0;
}