What is the main idea behind Strange Printer II?

Model each color by its bounding rectangle, then infer which colors must be printed earlier when another color appears inside that rectangle. The problem becomes cycle detection in a directed graph of color dependencies.

Why does topological sort work for this problem?

A color can be printed before every color that remains visible inside its forced rectangle. Those ordering constraints form a directed graph, and a valid printing sequence exists exactly when the graph has a topological order.

Why can I use the bounding rectangle of each color?

Because each color may be printed only once as a single rectangle. Any valid turn for that color must cover all of its final cells, so the minimal rectangle containing them is the only region that matters for dependency checks.

What makes Strange Printer II return false?

It returns false when the color dependencies form a cycle. In that case, each color requires another color to be printed first, so no color can legally be the last remaining layer.

Is graph indegree plus topological ordering the best pattern here?

Yes, it is the standard clean solution for this problem because the printer rules create ordering constraints between colors, not between individual cells. With at most 60 colors, the graph approach is both simpler and efficient enough.

#1591

Hard

auto_awesome图

LeetCode 题解工作台

奇怪的打印机 II

给你一个奇怪的打印机，它有如下两个特殊的打印规则：每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。一旦矩形根据上面的规则使用了一种颜色，那么相同的颜色不能再被使用。给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中 tar…

数组图拓扑排序矩阵

题目描述

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

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

给你一个初始没有颜色的 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

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The hint about thinking in reverse is a strong signal to identify which color could have been printed last.
question_mark
The small color range up to 60 suggests modeling colors as graph nodes instead of treating every cell as a state.
question_mark
If overlapping rectangles seem to force ordering constraints, the expected pattern is indegree plus topological ordering.

warning

常见陷阱

外企场景

error
Adding dependencies in the wrong direction is the most common bug; if color d appears inside color c's rectangle, then c must come before d.
error
Forgetting to deduplicate edges can inflate indegrees and make an acyclic Strange Printer II instance look impossible.
error
Trying to simulate forward painting cell by cell misses the one-rectangle-per-color rule and gets stuck on overwrite order.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Replace topological sort with repeated elimination: remove any color whose rectangle currently contains only itself or already removed colors.
arrow_right_alt
Ask for one valid print order instead of just true or false; the topological order directly provides it when no cycle exists.
arrow_right_alt
Generalize the same rectangle-dependency idea to grids where symbols form layers and the task is to detect cyclic overwrite constraints.

help

常见问题

外企场景

继续练习

#1632 矩阵转换后的排名 #1728 猫和老鼠 II #2328 网格图中递增路径的数目