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.
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 = [[0] * 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[0]):
mat[x][y] = 1 - mat[x][y]
def minFlips(self, mat):
m = len(mat)
n = len(mat[0])
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[0]