<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>

#include <vector>
using namespace std;
class Solution {
  /*
   * Flipping cell twice is same as not flipping at all, so we only need to
   * consider flipping a cell once. Operation is commutative and associative
   *
   * BF: Each index can be flipped or not flipped. Try every possible
   * combination and check if zero matrix is reached
   *
   * Use backtracking
   *
   * How to check if zero matrix achieved?
   */

  int ans;
  int m;
  int n;

  const vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

  inline int flip(int x) { return x == 0 ? 1 : 0; }

  void dfs(vector<vector<int>> &mat, int steps, int idx, int ones) {
    if (ones == 0) {
      ans = min(ans, steps);
      return;
    }

    if (idx == m * n) {
      return;
    }

    int i = idx / n;
    int j = idx % n;


    // Flip
    vector<vector<int>> newmat = mat;
    int newones = ones;
    if (newmat[i][j] == 1) {
      newones--;
    } else {
      newones++;
    }
    newmat[i][j] = flip(newmat[i][j]);
    for (const auto &d : dir) {
      int newi = i + d.first;
      int newj = j + d.second;
      if (newi >= 0 && newi < m && newj >= 0 && newj < n) {
        if (newmat[newi][newj] == 1) {
          newones--;
        } else {
          newones++;
        }
        newmat[newi][newj] = flip(newmat[newi][newj]);
      }
    }
    dfs(newmat, steps + 1, idx + 1, newones);

    // Don't flip
    dfs(mat, steps, idx + 1, ones);
  }

public:
  int minFlips(vector<vector<int>> &mat) {
    m = mat.size();
    n = mat[0].size();
    ans = INT_MAX;

    // Count ones
    int ones = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (mat[i][j] == 1) {
          ones++;
        }
      }
    }
    dfs(mat, 0, 0, ones);

    return ans == INT_MAX ? -1 : ans;
  }
};
13200