There is a strange printer with the following two special requirements:
On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
Once the printer has used a color for the above operation, the same color cannot be used again.
You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.
Return true if it is possible to print the matrix targetGrid, otherwise, return false.
Example 1:
Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true
Example 2:
Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true
Example 3:
Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
Example 4:
Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false
Constraints:
m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60
class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        R = len(targetGrid)
        C = len(targetGrid[0])
        WHITE = 0
        GRAY = 1
        BLACK = 2
        boxes = collections.defaultdict(lambda: [61, 61, -1, -1])
        
        for r, row in enumerate(targetGrid):
            for c, v in enumerate(row):
                boxes[v][0] = min(boxes[v][0], r)
                boxes[v][1] = min(boxes[v][1], c)
                boxes[v][2] = max(boxes[v][2], r)
                boxes[v][3] = max(boxes[v][3], c)
                
        graph = { color: set() for color in boxes }
        
        for color, (r1, c1, r2, c2) in boxes.items():
            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if targetGrid[r][c] != color:
                        graph[color].add(targetGrid[r][c])
                 
        state = collections.defaultdict(int)
        
        def dfs(u):
            state[u] = GRAY
            
            for v in graph[u]:
                if state[v] == WHITE:
                    if not dfs(v):
                        return False
                elif state[v] == GRAY:
                    return False
                
            state[u] = BLACK
            return True
        
        for s in graph:
            if state[s] == WHITE:
                if not dfs(s):
                    return False
                
        return True
class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        R = len(targetGrid)
        C = len(targetGrid[0])
        WHITE = 0
        GRAY = 1
        BLACK = 2
        boxes = collections.defaultdict(lambda: [61, 61, -1, -1])
        
        for r, row in enumerate(targetGrid):
            for c, v in enumerate(row):
                boxes[v][0] = min(boxes[v][0], r)
                boxes[v][1] = min(boxes[v][1], c)
                boxes[v][2] = max(boxes[v][2], r)
                boxes[v][3] = max(boxes[v][3], c)
                
        graph = { color: set() for color in boxes }
        
        for color, (r1, c1, r2, c2) in boxes.items():
            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if targetGrid[r][c] != color:
                        graph[color].add(targetGrid[r][c])
                 
        state = collections.defaultdict(int)
        
        def dfs(u):
            state[u] = GRAY
            
            for v in graph[u]:
                if state[v] == WHITE:
                    if not dfs(v):
                        return False
                elif state[v] == GRAY:
                    return False
                
            state[u] = BLACK
            return True
        
        for s in graph:
            if state[s] == WHITE:
                if not dfs(s):
                    return False
                
        return True