1591. Strange Printer II

题目信息

题号:

1591

难度:

Hard

主题:

矩阵、拓扑排序、依赖图

原题:

LeetCode 1591

重点:

每种颜色至多使用一次,每次覆盖一个实心矩形;后打印颜色可以覆盖先前颜色,判断能否得到目标网格

题目重述

奇怪打印机每次选择一种尚未使用过的颜色,并把一个轴对齐的实心矩形全部打印成该颜色。后续打印允许覆盖已有颜色,但同一种颜色最多使用一次。

给定目标颜色矩阵 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
解释:两种颜色的最小包围矩形都覆盖另一种颜色,形成无法满足的循环打印顺序。