Это интересная проблема BFS. Немного сложнее обычных, однако решение все равно очень стандартное.
Проблема в последнем конкурсе на этой неделе. Кажется, Leetcode снижает уровень сложности конкурса, чтобы отпраздновать Рождество (только мое предположение). Более 700 человек успешно решили все 4 вопроса конкурса.
1284. Минимальное количество переворотов для преобразования бинарной матрицы в нулевую матрицу
Время выполнения составляет 40 мс.
from collections import deque
class Solution:
def minFlips(self, A: List[List[int]]) -> int:
R, C = len(A), len(A[0])
a = [str(A[i][j]) for i in range(R) for j in range(C)]
a = ''.join(a)
if a == '0'*(R*C):return 0
def bfs(a):
flip = {'0':'1', '1':'0'}
open_list = deque([(a, 0)])
seen = {a}
while open_list:
state, d = open_list.popleft()
for i in range(R):
for j in range(C):
valids = [(i+di, j+dj) for di, dj in [(0, 1),(0, -1),(1, 0),(-1, 0)] if 0<=i+di<R and 0<=j+dj<C]
state_l = list(state)
for ii, jj in valids+[(i, j)]:
idx = C*ii + jj
state_l[idx] = flip[state_l[idx]]
state_new = ''.join(state_l)
if state_new == '0'*(R*C):return d+1
if state_new not in seen:
seen.add(state_new)
open_list.append((state_new, d+1))
return -1
return bfs(a)
Спасибо.
