---

1591. 奇怪的打印机 II

• 标签：图、拓扑排序、数组、矩阵
• 难度：困难

题目链接

• 1591. 奇怪的打印机 II - 力扣

题目大意

描述：给定一个 $m \times n$ 的矩阵 $targetGrid$，每个位置有颜色值 $1 \sim 60$。有一台打印机，每次操作可以选择一种颜色，将该颜色的一个连通区域（矩形区域）涂满该颜色，可以覆盖之前的颜色。

要求：判断是否能通过若干次操作得到 $targetGrid$。

说明：

• $1 \le m, n \le 60$。

示例：

• 示例 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

解题思路

思路 1：拓扑排序

1. 核心思想

对于每种颜色 $c$，找到它在 $targetGrid$ 中出现的边界（最上、最下、最左、最右）。这个边界矩形范围内的所有格子，要么是颜色 $c$，要么是在 $c$ 之上涂的其他颜色。

这意味着边界矩形内不是 $c$ 的颜色必须在 $c$ 之后涂。这构成一个偏序关系。

如果这个偏序关系有环（循环依赖），则不可能得到目标矩阵。

2. 具体步骤

第 1 步：找到每种颜色的边界 $[min\_row, max\_row, min\_col, max\_col]$。

第 2 步：遍历矩阵，对于每种颜色 $c$ 的边界矩形内：

• 如果某个格子的颜色 $other \neq c$，添加一条边 $c \to other$（表示 $c$ 先涂，$other$ 后涂）。

第 3 步：拓扑排序。如果存在环，返回 False，否则 True。

3. 举例说明

以 $targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]$ 为例：

颜色 $1$ 的边界 $[0,3,0,3]$，边界矩形内有颜色 $2$（在 $[1,2,1,2]$ 区域），说明 $1$ 必须在 $2$ 之前涂。

颜色 $2$ 的边界 $[1,2,1,2]$，边界矩形内只有 $2$。

拓扑排序：$1 \to 2$，无环，返回 True。

以 $targetGrid = [[1,2,1],[2,1,2],[1,2,1]]$ 为例：

颜色 $1$ 的边界 $[0,2,0,2]$，矩形内有颜色 $2$，$1 \to 2$。
颜色 $2$ 的边界 $[0,2,0,2]$，矩形内有颜色 $1$，$2 \to 1$。

存在环 $1 \leftrightarrow 2$，返回 False。

思路 1：代码

class Solution:
    def isPrintable(self, targetGrid: List[List[int]]) -> bool:
        m, n = len(targetGrid), len(targetGrid[0])
        # 每种颜色的边界
        bound = {}
        for i in range(m):
            for j in range(n):
                c = targetGrid[i][j]
                if c not in bound:
                    bound[c] = [i, i, j, j]  # min_r, max_r, min_c, max_c
                else:
                    bound[c][0] = min(bound[c][0], i)
                    bound[c][1] = max(bound[c][1], i)
                    bound[c][2] = min(bound[c][2], j)
                    bound[c][3] = max(bound[c][3], j)

        # 建图：c -> other，表示 c 必须在 other 之前
        graph = {c: set() for c in bound}
        indeg = {c: 0 for c in bound}

        for c, (min_r, max_r, min_c, max_c) in bound.items():
            for i in range(min_r, max_r + 1):
                for j in range(min_c, max_c + 1):
                    other = targetGrid[i][j]
                    if other != c and other not in graph[c]:
                        graph[c].add(other)
                        indeg[other] = indeg.get(other, 0) + 1

        # 拓扑排序
        from collections import deque
        q = deque([c for c in bound if indeg.get(c, 0) == 0])
        cnt = 0
        while q:
            c = q.popleft()
            cnt += 1
            for nxt in graph[c]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)

        return cnt == len(bound)

思路 1：复杂度分析

• 时间复杂度：$O(m \times n \times colors)$，最多 $60 \times 60 \times 60 = 2.16 \times 10^5$。
• 空间复杂度：$O(colors)$。