Description

Submission

class Solution {
    int n;
    bool checkOK(int state, vector<vector<int>>& statements, vector<int>& mark) {
        for(int i = 0; i < n; ++i) {
            if((state>>i)&1) {
                if(mark[i] == 2) mark[i] = 1;
                else if(mark[i] != 1) return false;
                for(int j = 0; j < n; ++j) {
                    if(statements[i][j] == 2) continue;
                    if(mark[j] == 2) mark[j] = statements[i][j];
                    else if(mark[j] != statements[i][j]) return false;
                }
            }
        }

        for(int i = 0; i < n; ++i) {
            int t = (state>>i)&1;
            if(t == 1 && mark[i] == 0) return false;
            if(t == 0 && mark[i] == 1) return false;
        }

        return true;
    }
public:
    int maximumGood(vector<vector<int>>& statements) {
        n = statements.size();

        vector<int> mark(n);
        int ret = 0;
        for(int state = 0; state < (1 << n); ++state) {
            fill(mark.begin(), mark.end(), 2); // initial state
            if(checkOK(state, statements, mark)) ret = max(ret, __builtin_popcount(state));
        }

        return ret;
    }
};

// 1110001:

// 1 good
// 0 bad


// 2^15 = 3e4
// 2^15*15*15 = 6e6


// [[2,2,2,2],
//  [1,2,1,0],
//  [0,2,2,2], 
//  [0,0,0,2]]