1591. 奇怪的打印机 II
来源第 35 场双周赛 Q4难度困难分数2290
题目描述
给你一个奇怪的打印机，它有如下两个特殊的打印规则：
- 每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
- 一旦矩形根据上面的规则使用了一种颜色，那么 相同的颜色不能再被使用 。
给你一个初始没有颜色的 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.lengthn == targetGrid[i].length1 <= m, n <= 601 <= targetGrid[row][col] <= 60
解法
方法一
思考
每次用一种新颜色打印一个矩形，且该颜色不能再用。要判断给定网格是否可由这种过程得到。同一颜色必须落在其最小包围矩形内，且该矩形里后打印的颜色会覆盖它。
对每种颜色求出行、列范围；范围内若出现其它颜色 \(c'\)，则 \(c'\) 必须晚于 \(c\) 打印，于是连一条 \(c\to c'\) 的约束边。约束图无环当且仅当存在合法打印顺序，可用拓扑排序判定。
1 | |
1 | |
1 | |
1 | |