拓扑排序题目：奇怪的打印机 II

题目

标题和出处

标题：奇怪的打印机 II

出处：1591. 奇怪的打印机 II

难度

8 级

题目描述

要求

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

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

给定一个m × n \texttt{m} \times \texttt{n}m×n的矩阵targetGrid \texttt{targetGrid}targetGrid，其中targetGrid[row][col] \texttt{targetGrid[row][col]}targetGrid[row][col]是位置(row, col) \texttt{(row, col)}(row, col)的颜色。

如果能按照上述规则打印出矩阵targetGrid \texttt{targetGrid}targetGrid，返回true \texttt{true}true，否则返回false \texttt{false}false。

示例

示例 1：

输入：targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]] \texttt{targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]}targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
输出：true \texttt{true}true

示例 2：

输入：targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]] \texttt{targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]}targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
输出：true \texttt{true}true

示例 3：

输入：targetGrid = [[1,2,1],[2,1,2],[1,2,1]] \texttt{targetGrid = [[1,2,1],[2,1,2],[1,2,1]]}targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
输出：false \texttt{false}false
解释：没有办法得到targetGrid \texttt{targetGrid}targetGrid，因为同一种颜色不能在多轮使用。

数据范围

• m = targetGrid.length \texttt{m} = \texttt{targetGrid.length}m=targetGrid.length
• n = targetGrid[i].length \texttt{n} = \texttt{targetGrid[i].length}n=targetGrid[i].length
• 1 ≤ m, n ≤ 60 \texttt{1} \le \texttt{m, n} \le \texttt{60}1≤m, n≤60
• 1 ≤ targetGrid[row][col] ≤ 60 \texttt{1} \le \texttt{targetGrid[row][col]} \le \texttt{60}1≤targetGrid[row][col]≤60

解法

思路和算法

由于每种颜色只能用于打印一个矩形，且同一种颜色只能使用一次，因此可以根据每种颜色在矩阵中出现的行下标和列下标的范围确定颜色的边界，并根据边界判断每种颜色的打印顺序。如果颜色b bb出现在颜色a aa的边界内，则颜色a aa在颜色b bb之前打印。

根据每种颜色的打印顺序，可以将所有的颜色和顺序看成有向图，如果颜色a aa在颜色b bb之前打印，则存在一条从a aa指向b bb的有向边。

首先遍历矩阵targetGrid \textit{targetGrid}targetGrid，得到矩阵中的每种颜色的边界，然后遍历矩阵并记录每种颜色的入度和后续颜色，得到不同颜色之间的相对打印顺序，建立有向图。

对于位置( i , j ) (i, j)(i,j)，执行如下操作。

1. 记curr = targetGrid [ i ] [ j ] \textit{curr} = \textit{targetGrid}[i][j]curr=targetGrid[i][j]，即当前位置的颜色是curr \textit{curr}curr。

2. 遍历矩阵中出现过的所有颜色，对于每种颜色prev \textit{prev}prev，如果prev ≠ curr \textit{prev} \ne \textit{curr}prev=curr且当前位置( i , j ) (i, j)(i,j)在颜色prev \textit{prev}prev的边界内，则颜色prev \textit{prev}prev在颜色curr \textit{curr}curr之前打印，将curr \textit{curr}curr的入度加1 11，将curr \textit{curr}curr添加到prev \textit{prev}prev的后续颜色中。

建立有向图之后，从入度为0 00的颜色开始拓扑排序，判断是否可以打印出矩阵targetGrid \textit{targetGrid}targetGrid。可以打印出矩阵targetGrid \textit{targetGrid}targetGrid的条件是所有颜色和相对打印顺序组成的有向图中没有环，此时可以按特定顺序打印所有颜色。如果有向图中有环，即不同颜色之间的相对打印顺序存在循环依赖，则不能打印所有颜色。

因此，判断是否可以打印出矩阵targetGrid \textit{targetGrid}targetGrid的方法是：在拓扑排序的过程中计算遍历过的颜色数量。如果遍历结束之后，遍历过的颜色数量等于矩阵中出现过的所有颜色数量，则可以打印出矩阵targetGrid \textit{targetGrid}targetGrid，返回true \text{true}true；否则不能打印出矩阵targetGrid \textit{targetGrid}targetGrid，返回false \text{false}false。

代码

classSolution{publicbooleanisPrintable(int[][]targetGrid){intmaxColor=0;intm=targetGrid.length,n=targetGrid[0].length;for(inti=0;i<m;i++){for(intj=0;j<n;j++){maxColor=Math.max(maxColor,targetGrid[i][j]);}}int[][]bounds=newint[maxColor+1][];for(inti=0;i<m;i++){for(intj=0;j<n;j++){intcolor=targetGrid[i][j];if(bounds[color]==null){bounds[color]=newint[]{i,i,j,j};}else{int[]bound=bounds[color];bound[0]=Math.min(bound[0],i);bound[1]=Math.max(bound[1],i);bound[2]=Math.min(bound[2],j);bound[3]=Math.max(bound[3],j);}}}int[]indegrees=newint[maxColor+1];List<Integer>[]nextArr=newList[maxColor+1];for(inti=1;i<=maxColor;i++){nextArr[i]=newArrayList<Integer>();}for(inti=0;i<m;i++){for(intj=0;j<n;j++){intcurr=targetGrid[i][j];for(intprev=1;prev<=maxColor;prev++){if(prev==curr||bounds[prev]==null){continue;}int[]bound=bounds[prev];if(i>=bound[0]&&i<=bound[1]&&j>=bound[2]&&j<=bound[3]){indegrees[curr]++;nextArr[prev].add(curr);}}}}intcount=0;Queue<Integer>queue=newArrayDeque<Integer>();for(intcolor=1;color<=maxColor;color++){if(indegrees[color]==0){queue.offer(color);}}while(!queue.isEmpty()){intcolor=queue.poll();count++;List<Integer>nextList=nextArr[color];for(intnext:nextList){indegrees[next]--;if(indegrees[next]==0){queue.offer(next);}}}returncount==maxColor;}}

复杂度分析

• 时间复杂度：O ( m n c ) O(mnc)O(mnc)，其中m mm和n nn分别是矩阵targetGrid \textit{targetGrid}targetGrid的行数和列数，c cc是矩阵中的不同颜色数量。计算颜色数量和每种颜色的边界需要O ( m n ) O(mn)O(mn)的时间，建立有向图需要O ( m n c ) O(mnc)O(mnc)的时间，拓扑排序需要O ( m n c ) O(mnc)O(mnc)的时间，因此时间复杂度是O ( m n c ) O(mnc)O(mnc)。

• 空间复杂度：O ( m n c ) O(mnc)O(mnc)，其中m mm和n nn分别是矩阵targetGrid \textit{targetGrid}targetGrid的行数和列数，c cc是矩阵中的不同颜色数量。存储每种颜色的边界需要O ( m n ) O(mn)O(mn)的空间，存储图需要O ( m n c ) O(mnc)O(mnc)的空间，队列需要O ( c ) O(c)O(c)的空间，因此空间复杂度是O ( m n c ) O(mnc)O(mnc)。