<p>Given a <code>m x n</code> binary matrix <code>mat</code>. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing <code>1</code> to <code>0</code> and <code>0</code> to <code>1</code>). A pair of cells are called neighbors if they share one edge.</p>

<p>Return the <em>minimum number of steps</em> required to convert <code>mat</code> to a zero matrix or <code>-1</code> if you cannot.</p>

<p>A <strong>binary matrix</strong> is a matrix with all cells equal to <code>0</code> or <code>1</code> only.</p>

<p>A <strong>zero matrix</strong> is a matrix with all cells equal to <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/11/28/matrix.png" style="width: 409px; height: 86px;" />
<pre>
<strong>Input:</strong> mat = [[0,0],[0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> mat = [[0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> Given matrix is a zero matrix. We do not need to change it.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,0,0],[1,0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> Given matrix cannot be a zero matrix.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 3</code></li>
	<li><code>mat[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

static auto init_io = []() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  return 0;
}();
using VEC = vector<int>;
class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        //if( m == 1 && n == 1 ) return mat[0][0] == 1;
        vector<VEC> flipTogether;
        int initVal = 0;
        flipTogether.resize(m * n);
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                //cout << "(" << i << ", " << j << ") can modify:" << endl;
                int idx = calIdx(m, i, j);
                flipTogether[idx].push_back(idx);
                if(i-1 >= 0) flipTogether[idx].push_back(calIdx(m, i - 1, j));
                if(i+1  < m) flipTogether[idx].push_back(calIdx(m, i + 1, j));
                if(j-1 >= 0) flipTogether[idx].push_back(calIdx(m, i, j - 1));
                if(j+1  < n) flipTogether[idx].push_back(calIdx(m, i, j + 1));

                initVal += mat[i][j] * (1 << idx);
            }
        }

        vector<int> queue;
        unordered_set<int> visited;
        queue.push_back(initVal);
        visited.insert(initVal);
        int flips = 0;
        while( !queue.empty() )
        {
            vector<int> nextQueue;
            for(auto&curVal : queue)
            {
                if(curVal == 0 ) return flips;
                for(int i = 0; i < m*n; i++)
                {
                    int newVal = curVal;
                    for(auto&m : flipTogether[i])
                    {
                        int bit = ( 1 << m );
                        newVal ^= bit;
                    }
                    //cout << i << ", " << curVal << ", " << newVal << endl;
                    if(!visited.count(newVal))
                    {
                        nextQueue.push_back(newVal);
                        visited.insert(newVal);
                    }
                }
            }
            swap(queue, nextQueue);
            flips++;
        }
        return -1;
    }
    int calIdx(int colNums, int row, int col)
    {
        //cout << "(" << row << ", " << col << ") can be modified." << endl;
        return col * colNums + row;
    }
};
8900