# Minimum Number of Flips to Convert Binary Matrix to Zero Matrix    ## Intuition

We had been given in the constraints that 1 <= m <= 3 and 1 <= n <= 3. So there are at most 9 nodes. And over all 2 ** 9 different status.

Each status could be thought as a vertex in a graph. 2 vertices p, q, are connected when we flip one node in p, it becomes q.

So the problem becaumes to calculate the minimum path from the given mat to an all zero matrix.

## Solution

``````
import collections

class Solution:
def index(self, mat):
ans = 0
for row in mat:
for v in row:
ans = (ans << 1) + v
return ans

def get_mat(self, index, m, n):
ans = [ * n for _ in range(m)]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
ans[i][j] = index % 2
index = index >> 1
return ans

def convert(self, mat, i, j):
for x, y in [(i, j), (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if 0 <= x < len(mat) and 0 <= y < len(mat):
mat[x][y] = 1 - mat[x][y]

def minFlips(self, mat):
m = len(mat)
n = len(mat)
visited = [-1] * (2 ** 9)
visited[self.index(mat)] = 0
queue = collections.deque([self.index(mat)])

while queue:
vertex = queue.popleft()
mat = self.get_mat(vertex, m, n)
for i in range(m):
for j in range(n):
self.convert(mat, i, j)
child = self.index(mat)
if visited[child] == -1:
visited[child] = visited[vertex] + 1
queue.append(child)
self.convert(mat, i, j)
return visited
``````