_.cc

#include <bits/stdc++.h>

using namespace std;

struct combinations {

    typedef vector<int> combination_t;
    bool completed;
    int generated;

    combinations(int N, int R) : completed(N < 1 || R > N), generated(0), N(N), R(R) {
        for (int c = 1; c <= R; ++c)
            curr.push_back(c);
    }

    combination_t next() {
        combination_t ret = curr;
        completed = true;
        for (int i = R - 1; i >= 0; --i) {
            if (curr[i] < N - R + i + 1) {
                int j = curr[i] + 1;
                while (i < R)
                    curr[i++] = j++;
                completed = false;
                ++generated;
                break;
            }
        }
        for (int i = 0; i < ret.size(); ++i)
            ret[i]--;
        return ret;
    }

private:
    int N, R;
    combination_t curr;
};

int remove_duplicates(bool** matrices, int rows, int cols) {
    bool mark[rows];
    for (int i = 0; i < rows; ++i) {
        mark[i] = false;
    }
    for (int i = 0; i < rows; ++i) {
        if (!mark[i]) {
            for (int j = i + 1; j < rows; ++j) {
                bool isequal = true;
                for (int k = 0; k < cols; ++k) {
                    if (matrices[i][k] != matrices[j][k]) {
                        isequal = false;
                        break;
                    }
                }
                if (isequal) {
                    mark[j] = true;
                }
            }
        }
    }
    int j = 0;
    for (int i = 0; i < rows; ++i) {
        if (!mark[i]) {
            for (int k = 0; k < cols; ++k) {
                matrices[j][k] = matrices[i][k];
            }
            j++;
        }
    }
    return j;
}

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

    bool** matrices = new bool*[k];
    for (int i = 0; i < k; ++i) {
        matrices[i] = new bool[n * m];
    }
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n*m; ++j) {
            char c;
            cin >> c;
            matrices[i][j] = (c == '1');
        }
    }

    k = remove_duplicates(matrices, k, n * m);
    if (k == 1) {
        cout << 0 << endl;
        return 0;
    } else if (k == 2) {
        cout << 1 << endl;
        return 0;
    }
    int initdiff = 1;
    if (k == 3 || k == 4)
        initdiff = 2;
    else if (k == 5 || k == 6)
        initdiff = 3;

    for (int diff = initdiff; diff <= 4; ++diff) {
        combinations allcombs(n * m, diff);
        while(!allcombs.completed) {
            vector<int> comb = allcombs.next();
            set<long> nums;
            bool found = true;
            for (int i = 0; i < k; ++i) {
                int cnum = 0;
                for (int j = 0; j < comb.size(); ++j) {
                    if (matrices[i][comb[j]])
                        cnum |= 1 << j;
                }
                if (nums.find(cnum) != nums.end()) {
                    found = false;
                    break;
                }
                nums.insert(cnum);
            }
            // cout << nums << endl;
            if (found) {
                cout << diff << endl;
                return 0;
            }
        }
    }
    cout << 5 << endl;
    return 0;
}