《 翻 之 》

题目描述

\hspace{15pt}对于给定的 nnn 行 mmm 列的矩阵，每一个元素要么是 ‘0’\texttt{`0'}‘0’，要么是 ‘1’\texttt{`1'}‘1’。
\hspace{15pt}每一轮，你可以进行一次以下操作：
∙ \hspace{23pt}\bullet\,∙选择一行的元素，将其全部反置，即 ‘0’\texttt{`0'}‘0’ 变为 ‘1’\texttt{`1'}‘1’，‘1’\texttt{`1'}‘1’ 变为 ‘0’\texttt{`0'}‘0’。
\hspace{15pt}请你帮助小歪判断，若能进行任意多轮操作（也可以不进行操作），至多能使得多少列的元素均为 ‘1’\texttt{`1'}‘1’。你只需要输出这个最大值。

输入描述:

\hspace{15pt}第一行输入两个正整数 n,m(1≦n,m≦3×103)n,m\left(1\leqq n,m\leqq 3 \times 10^3\right)n,m(1≦n,m≦3×103) 代表矩阵的行数和列数。
\hspace{15pt}此后 nnn 行，每行输入一个长度为 mmm 、仅由 ‘0’\texttt{`0'}‘0’ 和 ‘1’\texttt{`1'}‘1’ 构成的字符串，代表矩阵每一行中的元素。

输出描述:

\hspace{15pt}输出一个整数，表示至多能使得多少列的元素均为 ‘1’\texttt{`1'}‘1’。

示例1

输入

复制3 4 1111 1111 1111

3 4
1111
1111
1111

输出

复制4

4

说明

\hspace{15pt}在这个样例中，不需要进行操作，所有列的元素均为 ‘1’\texttt{`1'}‘1’。

示例2

输入

复制3 2 01 10 11

3 2
01
10
11

输出

复制1

1

说明

\hspace{15pt}在这个样例中，我们可以选择对第一行进行操作，使得第一行变为 "10"\texttt{"10"}"10"，此时，第一列的元素均为 ‘1’\texttt{`1'}‘1’。

C语言代码实现：

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

// 计算从 begin 到 end 列中，元素全为 1 的列数
int row(int begin, int end, int **a, int rows, int cols) {
    int i, j, co = 0;
    for (i = begin; i <= end; i++) {
        int flag = 0;
        for (j = 0; j < rows; j++) {
            if (a[j][i] == 0) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            co++;
        }
    }
    return co;
}

// 翻转指定行的元素，并返回操作后元素全为 1 的列数
int change(int be, int **a, int rows, int cols) {
    int i;
    for (i = 0; i < cols; i++) {
        if (a[be][i] == 0) {
            a[be][i] = 1;
        } else {
            a[be][i] = 0;
        }
    }
    return row(0, cols - 1, a, rows, cols);
}

int main() {
    int m, n, i, j, count = 0, count1 = 0;
    // 输入验证
    do {
       
        scanf("%d %d", &m, &n);
    } while (m <= 0 || n <= 0);

    // 动态分配二维数组内存
    int **a = (int **)malloc(m * sizeof(int *));
    for (i = 0; i < m; i++) {
        a[i] = (int *)malloc(n * sizeof(int));
    }

    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            scanf("%1d", &a[i][j]);
        }
    }

    count = row(0, n - 1, a, m, n);
    for (i = 0; i < m; i++) {
        count1 = change(i, a, m, n);
        if (count1 > count) {
            count = count1;
        }
    }

    printf("%d", count);

    // 释放动态分配的内存
    for (i = 0; i < m; i++) {
        free(a[i]);
    }
    free(a);

    return 0;
}