题解 | 小红的矩阵染色

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

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

int main() {
    int n, m, k;

    scanf("%d %d %d", &n, &m, &k);
    char arr[n][m];
    int nums[n * m];
    for (int i = 0; i < n; i ++) {
        scanf("%s", arr[i]);
    }

    int x = 0;
    for (int i = 0; i < m; i ++) {
        int count = 0;
        for (int j = 0; j < n; j ++) {
            char c = arr[j][i];
            if (c == 'o') {
                count++;
                if (j == n - 1) {
                    nums[x++] = count;
                }
                continue;
            }
            if (c == '*' && count > 0) {
                nums[x++] = count;
                count = 0;
            }
        }
    }
    qsort(nums, x, sizeof(int), compare);
    int maxstore = 0;
    for (int i = 0; i < x; i ++) {
        
        if (k < nums[i]) {
            maxstore += k-1;
        }else{
            maxstore += nums[i]-1;
        }
        k -= nums[i];
        if (k <= 0) {
            break;
        }
    }
    printf("%d\n", maxstore);
    return 0;
}