1591. Strange Printer II¶
题目信息¶
- 题号:
1591
- 难度:
Hard
- 主题:
矩阵、拓扑排序、依赖图
- 原题:
- 重点:
每种颜色至多使用一次,每次覆盖一个实心矩形;后打印颜色可以覆盖先前颜色,判断能否得到目标网格
题目重述¶
奇怪打印机每次选择一种尚未使用过的颜色,并把一个轴对齐的实心矩形全部打印成该颜色。后续打印允许覆盖已有颜色,但同一种颜色最多使用一次。
给定目标颜色矩阵 targetGrid,请判断是否存在一种打印顺序和对应矩形,使最终矩阵恰好等于目标。
1 <= targetGrid.length, targetGrid[i].length <= 60,颜色编号位于 1 到 60。
自建示例¶
单一颜色矩形可以一次完成:
输入:targetGrid = [[1,1],[1,1]]
输出:true
解释:使用颜色 1 打印整个 2 x 2 矩形即可。
交错颜色会形成相互覆盖依赖:
输入:targetGrid = [[1,2],[2,1]]
输出:false
解释:两种颜色的最小包围矩形都覆盖另一种颜色,形成无法满足的循环打印顺序。