# 1284 - Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
###### tags: `Hard`

* Question:
https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

1.可以選擇矩陣中的一個元素及它的上下左右元素進行翻轉(flip)
2.翻轉兩次又回到原點
3.題目輸入矩陣大小不超過3x3，所以可以直接暴力解

* Reference:
https://hackmd.io/@Zero871015/LeetCode-1284

Key:
1. Brute force
2. BFS
以翻轉次數作為level，先設定queue跟visited來將要檢查和翻轉的矩陣丟入queue中，檢查過的就丟入visited，為了產生n次翻轉的所有可能矩陣，每次迴圈(first for loop)結束就代表第i次可能已經遍尋完，且翻轉結果也存到queue中。
翻轉則是使用兩個for loop控制行和列位置來翻轉。
最後queue沒有矩陣就代表，所有結果已經遍尋完，裡面沒有zero matrix。
## Brute force solution

class Solution {
public:
    //TODO: For debug, show the matrix context.
    void show(vector<vector<int>>& mat)
    {
        int sx = mat[0].size();
        int sy = mat.size();
        for(int i = 0; i < sy; i++)
        {
            for(int j = 0; j < sx; j++)
                cout << mat[i][j] << " ";
            cout << endl;
        }
    }
    
    //TODO: Flip the cell you chosen and its neighboors.
    void trigger(vector<vector<int>>& mat,int x, int y)
    {
        int sx = mat[0].size() - 1;
        int sy = mat.size() - 1;
        
        mat[y][x] ^= 1;
        
        if(x != 0) mat[y][x-1] ^= 1;
        if(y != 0) mat[y-1][x] ^= 1;
        if(x !=sx) mat[y][x+1] ^= 1;
        if(y !=sy) mat[y+1][x] ^= 1;
    }
    
    //TODO: Check the matrix is equal to zero or not. 
    bool isZero(vector<vector<int>> mat)
    {
        int sx = mat[0].size();
        int sy = mat.size();
        for(int i = 0; i < sy; i++)
        {
            for(int j = 0; j < sx; j++)
                if(mat[i][j]!=0) return false;
        }
        return true;
    }
    
    int findMin(vector<vector<int>>& mat)
    {
        int sx = mat[0].size();
        int sy = mat.size();
        int min = 100;
        for(int k = 1; k < pow(2,sx*sy); k++)
        {
            vector<vector<int>> tempMat = mat;
            int temp = k;
            int count = 0;
            int score = 0;
            while(temp != 0)
            {
                if(temp%2==1)
                {
                    trigger(tempMat,count%sx,count/sx);
                    score++;
                }
                temp/=2;
                count++;
            }
            if(isZero(tempMat))
                min = min<score?min:score;
        }
        return min==100?-1:min;
    }
    
    int minFlips(vector<vector<int>>& mat) {
        if(isZero(mat)) return 0;
        //show(mat);
        return findMin(mat);
    }
};

## BFS Solution

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        // Check corner cases
        int m = mat.size();
        int n = m ? mat[0].size() : 0;
        if(m < 1 or n < 1) { return -1; }

        // Prepare for BFS
        set<vector<vector<int>>> visited;
        queue<vector<vector<int>>> q;
        q.push(mat);
        visited.insert(mat);

        int steps = 0;
        while(!q.empty()) {
            for(int sz = q.size() - 1; sz >= 0; --sz) {
                vector<vector<int>> cur = q.front();
                q.pop();

                // 已經成功翻成全部都是 0
                if(allZero(cur)) {
                    return steps;
                }

                for(int r = 0; r < m; ++r) {
                    for(int c = 0; c < n; ++c) {
                        // 以 (r,c) 為中心翻一次 matrix
                        flip(cur, m, n, r, c);

                        // 如果還沒走過這個盤面，放入 queue
                        if(!visited.count(cur)) {
                            q.push(cur);
                            visited.insert(cur);
                        }

                        // 把盤面翻回來
                        flip(cur, m, n, r, c);
                    }
                }
            }

            ++steps;
        }

        return -1;
    }

private:
    void flip(vector<vector<int>>& mat, int& m, int& n, int& r, int& c) {
        // 翻鄰居
        if(r - 1 >= 0) { mat[r-1][c] = (mat[r-1][c] == 1) ? 0 : 1; }
        if(r + 1 < m)  { mat[r+1][c] = (mat[r+1][c] == 1) ? 0 : 1; }
        if(c - 1 >= 0) { mat[r][c-1] = (mat[r][c-1] == 1) ? 0 : 1; }
        if(c + 1 < n)  { mat[r][c+1] = (mat[r][c+1] == 1) ? 0 : 1; }

        // 翻(r,c)
        mat[r][c] = (mat[r][c] == 1) ? 0 : 1;
    }
//the only purpose is checking the mat is zero or not, so use const to avoid changing the mat
    bool allZero(const vector<vector<int>>& mat) {
        for(int i = 0; i < mat.size(); ++i) {
            for(int j = 0; j < mat[0].size(); ++j) {
                if(mat[i][j] != 0) {
                    return false;
                }
            }
        }

        return true;
    }
};