# Участник:Ковальков Антон М05-903б/Strange Printer II

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Python3

```class Solution:
def isPrintable(self, targetGrid: List[List[int]]) -> bool:

def isUncoveredRect(grid, color, colorRects, printed):
startRow, startCol, endRow, endCol = colorRects[color]
for row in range(startRow, endRow):
for col in range(startCol, endCol):
if grid[row][col] != color and printed[grid[row][col]]:
return False
return True

def unprint(targetGrid, color, colorRects, printed, memo):
if tuple(printed.values()) in memo:
return memo[tuple(printed.values())]

printed[color] = False
if not any(printed.values()):
return True

for printedColor in printed:
if printed[printedColor] and isUncoveredRect(targetGrid, printedColor, colorRects, printed):
if unprint(targetGrid, printedColor, colorRects, printed, memo):
return True

printed[color] = True
memo[tuple(printed.values())] = False
return False

if len(targetGrid) < 1:
return False

colorRects = {}
for row in range(len(targetGrid)):
for col in range(len(targetGrid[0])):
color = targetGrid[row][col]
if color not in colorRects:
colorRects[color] = (row, col, row + 1, col + 1)
else:
oldRow, oldCol, oldEndRow, oldEndCol = colorRects[color]
colorRects[color] = (oldRow, min(oldCol, col), row + 1, max(oldEndCol, col + 1))

printed = { color: True for color in colorRects }
memo = {}
for color in printed:
if isUncoveredRect(targetGrid, color, colorRects, printed) and unprint(targetGrid, color, colorRects, printed, memo):
return True
return False```