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

import copy

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        r, c = len(mat), len(mat[0])
        min_flips = inf

        def flip(matrix, r, c):
            print("flip: r %s, c %s" % (r, c))
            matrix[r][c] = (matrix[r][c] + 1) % 2
            for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if 0 <= r + i < len(matrix) and 0 <= c + j < len(matrix[0]):
                    matrix[r+i][c+j] = (matrix[r+i][c+j] + 1) % 2

        def try_it(matrix, flips_so_far):
            for r, row in enumerate(matrix):
                for c, col in enumerate(row):
                    if r == 0:
                        continue
                    if matrix[r-1][c] == 1:
                        flip(matrix, r, c)
                        flips_so_far += 1
            if sum(matrix[-1]) == 0:
                nonlocal min_flips
                min_flips = min(min_flips, flips_so_far)

        combos = deque([[]])
        for i in range(len(mat[0])):
            while len(combos[0]) <= i:
                p = combos.popleft()
                combos.append(p + [0])
                combos.append(p + [1])
        for combo in combos:
            mat_copy = copy.deepcopy(mat)
            print("combo: "+str(combo))
            for b, bit in enumerate(combo):
                if bit:
                    print("b: "+str(b))
                    flip(mat_copy, 0, b)
            try_it(mat_copy, sum(combo))

        return min_flips if min_flips < inf else -1



16700