拓扑排序题目：奇怪的打印机 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}mtargetGrid.lengthn targetGrid[i].length \texttt{n} \texttt{targetGrid[i].length}ntargetGrid[i].length1 ≤ m, n ≤ 60 \texttt{1} \le \texttt{m, n} \le \texttt{60}1≤m, n≤601 ≤ 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)执行如下操作。记curr targetGrid [ i ] [ j ] \textit{curr} \textit{targetGrid}[i][j]currtargetGrid[i][j]即当前位置的颜色是curr \textit{curr}curr。遍历矩阵中出现过的所有颜色对于每种颜色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){intmaxColor0;intmtargetGrid.length,ntargetGrid[0].length;for(inti0;im;i){for(intj0;jn;j){maxColorMath.max(maxColor,targetGrid[i][j]);}}int[][]boundsnewint[maxColor1][];for(inti0;im;i){for(intj0;jn;j){intcolortargetGrid[i][j];if(bounds[color]null){bounds[color]newint[]{i,i,j,j};}else{int[]boundbounds[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[]indegreesnewint[maxColor1];ListInteger[]nextArrnewList[maxColor1];for(inti1;imaxColor;i){nextArr[i]newArrayListInteger();}for(inti0;im;i){for(intj0;jn;j){intcurrtargetGrid[i][j];for(intprev1;prevmaxColor;prev){if(prevcurr||bounds[prev]null){continue;}int[]boundbounds[prev];if(ibound[0]ibound[1]jbound[2]jbound[3]){indegrees[curr];nextArr[prev].add(curr);}}}}intcount0;QueueIntegerqueuenewArrayDequeInteger();for(intcolor1;colormaxColor;color){if(indegrees[color]0){queue.offer(color);}}while(!queue.isEmpty()){intcolorqueue.poll();count;ListIntegernextListnextArr[color];for(intnext:nextList){indegrees[next]--;if(indegrees[next]0){queue.offer(next);}}}returncountmaxColor;}}复杂度分析时间复杂度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)。