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

Материал из DISCOPAL
< Участник:Ковальков Антон М05-903б
Версия от 17:56, 23 декабря 2020; Ковальков Антон М05-903б (обсуждение | вклад) (Новая страница: «[https://leetcode.com/problems/strange-printer-ii/ https://leetcode.com/problems/strange-printer-ii/] Python3 <code-python> class Solution: def isPrintable(…»)

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

https://leetcode.com/problems/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