LeetCode 1591. 奇怪的打印机 II --判断排序

1591. 奇怪的打印机 II
      给你一个奇怪的打印机，它有如下两个特殊的打印规则：

每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
一旦矩形根据上面的规则使用了一种颜色，那么 相同的颜色不能再被使用 。
给你一个初始没有颜色的 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.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

题解

就是排序啊，如果排序后还存在不符合排序结果的数据，就说明不能打印出来。

AC代码

class Solution {
    
public:
    struct Node
    {
    
        int x1,y1,x2,y2,key;
    }arr[61];
    vector<Node>q;
    //判断a1.key类型的区域中是否出现了a2.key
    bool check(Node a1, Node a2, vector<vector<int>>& targetGrid)
    {
    
        for(int i=a1.x1;i<=a1.x2;i++)
        {
    
            for(int j=a1.y1;j<=a1.y2;j++)
            {
    
                if(targetGrid[i][j]==a2.key)return true;
            }
        }
        return false;
    }
    bool isPrintable(vector<vector<int>>& targetGrid) 
    {
    
        for(int i=1;i<=60;i++)
        {
    
            arr[i].x1 = 1e9;
            arr[i].y1 = 1e9;
            arr[i].x2 = -1e9;
            arr[i].y2 = -1e9;
        }
        for(int i=0;i<targetGrid.size();i++)
        {
    
            for(int j=0;j<targetGrid[i].size();j++)
            {
    
                int key = targetGrid[i][j];
                arr[key].x1 = min(arr[key].x1, i);
                arr[key].y1 = min(arr[key].y1, j);
                arr[key].x2 = max(arr[key].x2, i);
                arr[key].y2 = max(arr[key].y2, j);
                arr[key].key = key;
            }
        }
        for(int i=1;i<=60;i++)
        {
    
            q.push_back(arr[i]);
        }
        //这里做一次排序处理
        for(int i=0;i<q.size();i++)
        {
    
            for(int j=i+1;j<q.size();j++)
            {
    
                if(check(q[j],q[i],targetGrid))//q[j]区域出现了q[i]，说明q[j]应该在q[i]前面
                {
    
                    swap(q[i],q[j]);
                }
            }
        }
        //这里判断排序后的结果，是否存在冲突
        for(int i=0;i<q.size();i++)
        {
    
            for(int j=i+1;j<q.size();j++)
            {
    
                if(check(q[j],q[i],targetGrid))//q[j]区域出现了q[i]，q[j]在q[i]前面
                {
    
                    return false;
                }
            }
        }
        return true;
    }
};