奇怪的打印机 II

难度: Hard

给你一个奇怪的打印机，它有如下两个特殊的打印规则：

每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
一旦矩形根据上面的规则使用了一种颜色，那么 相同的颜色不能再被使用 。

给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中 targetGrid[row][col] 是位置 (row, col) 的颜色。

如果你能按照上述规则打印出矩形 targetGrid ，请你返回 true ，否则返回 false 。

示例 1：

输入：targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
输出：true

示例 2：

输入：targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
输出：true

示例 3：

输入：targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
输出：false
解释：没有办法得到 targetGrid ，因为每一轮操作使用的颜色互不相同。

示例 4：

输入：targetGrid = [[1,1,1],[3,1,3]]
输出：false

提示：

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

Submission

运行时间: 83 ms

内存: 16.2 MB

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        dict = {}
        m, n = len(targetGrid), len(targetGrid[0])
        for i in range(m):
            for j in range(n):
                color = targetGrid[i][j]
                if color not in dict:
                    dict[color] = [i, i, j, j]
                else:
                    dict[color][1] = i
                    dict[color][2] = min(dict[color][2], j)
                    dict[color][3] = max(dict[color][3], j)
        def can_be_grid(bound, color):
            up, down, left, right = bound
            for i in range(up, down + 1):
                for j in range(left, right + 1):
                    if targetGrid[i][j] not in [color, -1]:
                        return False
            return True
        while dict:
            flag = False
            remove = []
            for key, value in dict.items():
                if can_be_grid(value, key):
                    flag = True
                    for i in range(value[0], value[1] + 1):
                        for j in range(value[2], value[3] + 1):
                            targetGrid[i][j] = -1
                    remove.append(key)
            for key in remove:
                dict.pop(key)
            if not flag:
                return False
        return True

Explain

此题解采用了模拟打印机打印过程的方法。首先，使用一个字典记录每种颜色最初和最终出现的行和列（形成一个边界框），这意味着如果颜色c在一个矩形区域内完整存在，则理论上可以通过一次打印操作实现该颜色。之后，对每个颜色尝试执行打印操作：检查其边界框内是否所有颜色都能匹配目标或已被覆盖（值为-1）。如果可以，那么该颜色对应的区域就被设置为-1以表示该区域已被完全打印覆盖。该过程反复进行，直到没有颜色可以成功打印（返回false）或所有颜色都被打印完（返回true）。

时间复杂度: O(C * m * n)

空间复杂度: O(C)

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        dict = {}
        m, n = len(targetGrid), len(targetGrid[0])
        for i in range(m):
            for j in range(n):
                color = targetGrid[i][j]
                if color not in dict:
                    dict[color] = [i, i, j, j]  # 初始化颜色的边界
                else:
                    dict[color][1] = i  # 更新底部边界
                    dict[color][2] = min(dict[color][2], j)  # 更新左边界
                    dict[color][3] = max(dict[color][3], j)  # 更新右边界
        def can_be_grid(bound, color):
            up, down, left, right = bound
            for i in range(up, down + 1):
                for j in range(left, right + 1):
                    if targetGrid[i][j] not in [color, -1]:
                        return False
            return True
        while dict:
            flag = False
            remove = []
            for key, value in dict.items():
                if can_be_grid(value, key):
                    flag = True
                    for i in range(value[0], value[1] + 1):
                        for j in range(value[2], value[3] + 1):
                            targetGrid[i][j] = -1  # 打印覆盖
                    remove.append(key)
            for key in remove:
                dict.pop(key)  # 删除已打印的颜色
            if not flag:
                return False
        return True

Explore

在题解中使用字典来记录每种颜色的边界框是因为字典提供了更高效的颜色到其边界框映射的访问方式。使用字典，可以直接通过颜色值作为键快速查找和更新对应颜色的边界框信息。如果使用数组或列表，则可能需要额外的步骤来确定哪个索引或位置对应哪个颜色，这会增加复杂性和可能的计算开销。此外，颜色的数量和具体值可能是不连续的，使用字典可以更灵活地处理这种情况。

在打印检查函数`can_be_grid`中，判断条件包括`-1`是因为`-1`代表了该区域已经被打印处理。这意味着当我们检查一个颜色的边界框是否可以通过一次打印操作成功覆盖时，只需关注尚未打印的区域（即未标记为`-1`的区域）和当前颜色。包含`-1`作为有效条件允许算法忽视已经成功打印过的区域，从而只关注剩余未处理的部分。

将区域设置为-1表示该区域已被打印覆盖，确实有可能影响后续的颜色判断，尤其是如果多个颜色的打印区域有重叠时。为了避免这种问题，算法中在每次成功打印一个颜色并将对应区域设置为-1后，会从记录颜色边界的字典中移除该颜色。这样，在后续迭代中，已处理的颜色不会再次参与判断，从而避免了重叠后的错误覆盖或干扰。

题解中这种做法是基于假设：如果在任何迭代轮次中发现没有颜色可以被成功打印，这表明存在至少一个颜色的边界框内包含了其他不可移除的颜色，导致无法继续进行打印。这种情况意味着无法通过有限次的打印操作达到目标，因此返回`false`是合理的。虽然这是一个较为严格的判断，但按照题目逻辑和打印机操作的模拟，这种处理是符合实际情况的，不会漏掉特殊情况。