本文共 7380 字，大约阅读时间需要 24 分钟。

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]Output: falseExplanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]Output: false

Constraints:

• m == targetGrid.length
• n == targetGrid[i].length
• 1 <= m, n <= 60
• 1 <= targetGrid[row][col] <= 60

题意：给出一个奇特的打印机，它的打印规则如下：

• 每次操作时，打印机会使用同一种颜色打印一个矩形（矩形中的所有格子都使用这种颜色），每次打印都会覆盖矩形对应格子中原本的颜色；
• 一旦矩阵根据上一规则使用了一种颜色，就不能再在后面使用这种颜色。

给出一个目标矩阵 targetGrid ，它的大小为 m × n，判断使用初始没有任何颜色的同样大小的矩阵，是否能够根据上述规则打印成目标矩阵。

思路1 逆序模拟

比赛的时候没有做出来。这道题说起来应该是一道模拟题，或者说是贪心题。如果从初始矩阵顺着推断，几乎不可能做出这道题；所以破解之处在于，既然已经有了目标矩阵 targetGrid ，那么我们是否能够还原回原来的初始矩阵？

如果当前一种颜色出现在某个 完整矩形 里，我们就可以认为这种颜色是最后打印的颜色之一，比如下图中，颜色 4, 5 都出现完整矩形中，那么我们就可以先还原掉颜色 4 或者颜色 5（最后打印这两种颜色）。还原后，我们就回到了 Print with color 3 这种状态，注意：颜色 4 或颜色 5 所在的位置，下面是什么颜色不重要，反正它们会被覆盖掉。这样虽然最终状态下，颜色 3 只占据了 3 个格子，而 targetGrid[2][3] = 4 ，但是无所谓了，我们可以把这个格子也认为是 3 ，于是颜色 3 的矩形就完整了，我们还原掉颜色 3 的矩形。最后我们还原掉颜色 1 的矩形，得到初始矩阵。从而能够判断，可以从初始矩阵打印出目标矩阵：

这道题就是模拟这个倒过来的过程，也就是说，我们先删除最上层的颜色矩形，然后逐层删除没有被其他颜色覆盖的颜色矩形……emmm，说是这样说，算法如何实现还是一个问题。有些重要的点写在下面：

• 对于一种颜色，我们需要知道矩形的范围，寻找它的左边界、右边界、上边界和下边界，或者说两个坐标 (l, u), (r, b) ——左上坐标和右下坐标。我们还原这个范围的颜色矩形就可以了。
• 如果判断矩形是否完整？我们已经得到了矩形的范围，那么标准大小就等于 (r - l + 1) * (b - u + 1) 个格子，如果矩形的实际格子（没有被其他颜色覆盖的格子）数目等于标准大小，说明矩形是完整的。

算法的具体过程如下：

• 先找到一个未被还原的、完整的颜色矩形，它的标准大小等于实际大小；
• 设置这个颜色矩形已经被还原，然后对矩形中的所有格子，如果它在其他未被还原的颜色格子内部，就解锁这个格子（它可以被其他矩形使用）。最后设置这个格子已经被解锁；
• 这样持续循环，直到某一轮中，找不到能够还原的矩形，就退出循环。
• 循环所有颜色矩形，如果还有矩形无法还原，就返回 false 。都能被还原，表示能够回到初始矩形，返回 true 。

实际代码如下：

const int MAXM = 65;const int MAXN = 65;struct Color {
       bool enabled = false;     int l, r, u, b; //颜色矩阵的范围(l,u),(r,b)    int cnt, size;  //颜色矩阵的标准大小,实际大小(标准大小减去被覆盖的格子数)    Color() {
   }     Color(int x, int y) {
     //初始化颜色的范围和大小        u = b = x; l = r = y;         size = 1; cnt = 0; //size==cnt时就认为这个矩形是完整的,可以被还原        enabled = true;    //是否已经遇到(true表示已经遇到); 是否已经被还原(false表示已经被还原,之后这个矩形的格子可以随意使用)    }    void update(int x, int y) {
    //更新矩形范围和标准大小        l = min(l, y); r = max(r, y);        u = min(u, x); b = max(b, x);        size = (r - l + 1) * (b - u + 1);    }    bool inner(int x, int y) {
    //判断坐标是否在颜色矩形中        if (u <= x && x <= b && l <= y && y <= r) return true;        return false;    }} color[MAXM];int rea[MAXM][MAXN];class Solution {
   public:    bool isPrintable(vector
   
    
     >& targetGrid) {
           int m = targetGrid.size(), n = targetGrid[0].size();        for (int i = 1; i <= 60; ++i) {
               color[i].enabled = false; //所有颜色开始都没有遇到            color[i].cnt = 0;         //所有颜色矩形的实际格子数量开始都是0        }        for (int i = 0; i < m; ++i) {
               for (int j = 0; j < n; ++j) {
                   //Init                rea[i][j] = false;             //全部初始化为false                //Color                int c = targetGrid[i][j];                if (color[c].enabled == false) //之前没有遇到这种颜色                    color[c] = Color(i, j);    //初始化这种颜色矩形的范围和大小                else color[c].update(i, j);    //之前遇到过这种颜色,更新其范围和标准大小                ++color[c].cnt;                //更新这种颜色矩形中的实际格子数量            }        }        bool flag = false;        do {
               flag = false;            for (int c = 1; c <= 60 && !flag; ++c) {
    //循环所有颜色                //如果颜色矩形已经被还原或不是完整矩形,就跳过                if (color[c].enabled == false || color[c].size > color[c].cnt) continue;                 color[c].enabled = false; //还原这个颜色矩形                flag = true; //设置为true,表示还原过矩形(和冒泡排序提前退出的标志一样)                for (int i = color[c].u; i <= color[c].b; ++i) {
        //对这种颜色的上下范围                    for (int j = color[c].l; j <= color[c].r; ++j) {
    //对这种颜色的左右范围                        if (rea[i][j]) continue;                     //如果已经被解锁,不需要再被解锁,就跳过                        //用这个格子,解锁其他颜色矩形的格子                        for (int nc = 1; nc <= 60; ++nc) {
              //再次循环所有颜色矩形                            if (color[nc].enabled == false) continue;   //如果这一颜色矩形已经被还原,跳过                            if (color[nc].inner(i, j)) ++color[nc].cnt; //如果这个格子被包括在其他未还原的矩形的范围内                            //修改其他颜色矩形的实际格子数量                        }                        rea[i][j] = true; //这一格子已经被解锁                    }                }                //还原了某一矩形                //printf("Color %d %d %d\n", c, color[c].size, color[c].cnt);            }        } while (flag); //没有矩形要还原时直接退出        for (int c = 1; c <= 60; ++c) if (color[c].enabled) return false; //如果还有颜色未被还原,返回false        return true;    }};
    
   

效率如下：

执行用时：68 ms, 在所有 C++ 提交中击败了94.19% 的用户内存消耗：13.4 MB, 在所有 C++ 提交中击败了94.96% 的用户

思路2 拓扑排序

这一道题目也可以将问题转换为有向图。在 targetGrid 中，首先求出每个矩形的范围。然后再次扫描矩阵，如果某个颜色点 B 存在于矩形 A 中（以颜色代表矩形），则颜色矩形 A 应该先被打印，后打印 B ，即存在一条 A->B 的有向边。这样，如果一个颜色矩形 T 跨越了多种颜色矩形的范围，T 就必须等待所有在它下层的颜色矩形打印后再被打印。据此建立一张有向图。

采用邻接表，其中每个顶点 color 表示一种颜色矩形，它的有向邻接边表示 color 先被打印，邻接点的颜色矩形后被打印。于是，对邻接表进行拓扑排序，判断这张有向图是否是有向无环图，就可以判断是否可以从初始矩阵打印出目标矩阵。

代码如下：

class Solution {
   public:    vector
   
    
     > adjList;    int top[61], bottom[61], left[61], right[61]; //上下左右    bool isPrintable(vector
     
      
       >& targetGrid) {
           int color, m = targetGrid.size(), n = targetGrid[0].size();        for (int i = 1; i <= 60; ++i) {
               top[i] = left[i] = 61;            bottom[i] = right[i] = 0;        }        //遍历图中的像素,求出每种颜色的矩形范围        for (int r = 0; r < m; ++r) {
               for (int c = 0; c < n; ++c) {
                   color = targetGrid[r][c];                top[color] = min(top[color], r);                bottom[color] = max(bottom[color], r);                left[color] = min(left[color], c);                right[color] = max(right[color], c);            }        }        adjList.resize(61); //邻接表建立有向图        vector
       
        
         > haveEdge(61, vector
         
          (61, false)); //判断是否有边,避免重复添加 vector
          
            indegrees(61, 0); //入度数组 for (int r = 0; r < m; ++r) { for (int c = 0; c < n; ++c) { color = targetGrid[r][c]; for (int cl = 1; cl <= 60; ++cl) { if (color != cl && !haveEdge[cl][color] && r >= top[cl] && r <= bottom[cl] && c <= right[cl] && c >= left[cl]) { //这个格子在这种颜色矩形的范围内 haveEdge[cl][color] = true; ++indegrees[color]; adjList[cl].push_back(color); } } } } //进行拓扑排序,如果最后存在入度不为零的颜色,说明存在环,不能打印 queue
           
             q; for (int i = 1; i <= 60; ++i) if (indegrees[i] == 0) q.push(i); while (!q.empty()) { color = q.front(); q.pop(); for (int v : adjList[color]) { --indegrees[v]; if (indegrees[v] == 0) q.push(v); } } for (int i = 1; i <= 60; ++i) if (indegrees[i] > 0) return false; return true; }};
           
          
         
        
       
      
     
    
   

比起模拟来说，效率低许多，但好歹能过，而且程序更加清晰：

执行用时：380 ms, 在所有 C++ 提交中击败了19.09% 的用户内存消耗：20.7 MB, 在所有 C++ 提交中击败了20.58% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108764195 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！