Description

Submission

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int initialState = 0;

        int n = mat.size();
        int m = mat[0].size();

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(mat[i][j])initialState += 1 << (i * m + j);
            }
        }

        queue<int> q;
        unordered_set<int> visited;
        q.push(initialState);

        const int dirs[] = {-1, 0, 1, 0, -1};
        
        int ret = 0;
        while(!q.empty()) {
            int cnt = q.size();

            while(cnt--) {
                int cur = q.front();
                q.pop(); 

                if(cur == 0) return ret;

                if(visited.count(cur)) continue;
                visited.insert(cur);

                for(int i = 0; i < n; ++i) {
                    for(int j = 0; j < m; ++j) {
                        int t = cur;
                        for(int k = 0; k < 4; ++k) {
                            int x = i + dirs[k];
                            int y = j + dirs[k+1];
                            if(x < 0 || y < 0 || x >= n || y >= m) continue;
                            t ^= (1 << (x * m + y));
                        }
                        t ^= (1 << (i * m + j));
                        if(visited.count(t)) continue;
                        q.push(t);
                    }
                }
            }
            ++ret;
        }
        return -1;
    }
};


// 0 0 0 1
// 1 0 1 0
// 1 1 1 1  8 + 4 + 2 + 1 = 15

// 0
// 1
// 1

// 0 1 1 -> 101, 100, 000