【逆向思考】【拓扑排序】1591. 奇怪的打印机 II

本文涉及的知识点

逆向思考拓扑排序

LeetCode1591. 奇怪的打印机 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

拓扑排序

给颜色x盖章，一定从最左上的x，改到最右下的x，否则会依赖。
逆向思考，从后向前思考。给x盖的时候，这个区域除了x，都已经处理。
用拓扑排序。
如果x所在的矩形包括y，此存在边边x $\rightarrow$ y

代码

核心代码

class CTopSort
{
public:	template <class T = vector<int> >void Init(const vector<T>& vNeiBo,bool bDirect = true ){const int iDelOutDeg = bDirect ? 0 : 1;m_c = vNeiBo.size();m_vBackNeiBo.resize(m_c);vector<int> vOutDeg(m_c);for (int cur = 0; cur < m_c; cur++){vOutDeg[cur] = vNeiBo[cur].size();	for (const auto& next : vNeiBo[cur]){m_vBackNeiBo[next].emplace_back(cur);}}vector<bool> m_vHasDo(m_c);queue<int> que;for (int i = 0; i < m_c; i++){if ( vOutDeg[i] <= iDelOutDeg){m_vHasDo[i] = true;if (OnDo(i)) {que.emplace(i);}}}while (que.size()){const int cur = que.front();que.pop();for (const auto& next : m_vBackNeiBo[cur]){if (m_vHasDo[next] ){continue;}				vOutDeg[next]--;if (vOutDeg[next] <= iDelOutDeg ){m_vHasDo[next] = true;if (OnDo(next)) {que.emplace(next);}}}};}int m_c;
protected:virtual bool OnDo( int cur) = 0;vector<vector<int>> m_vBackNeiBo;	};
class CMyTopSort : public CTopSort
{
public:int m_iCount = 0;virtual bool OnDo(int cur) override{m_iCount++;return true;}
};
class Solution {
public:bool isPrintable(const vector<vector<int>>& targetGrid) {vector<unordered_set<int>> vNeiBo(61);for (int x = 1; x <= 60; x++){int l = 100, t = 100, right = -1, b = -1;for (int r = 0; r < targetGrid.size(); r++){for (int c = 0; c < targetGrid.front().size(); c++){if (targetGrid[r][c] == x){l = min(l, c);right = max(right, c);t = min(t, r);b = max(b, r);}}}for (int r = t; r <= b; r++){for (int c = l; c <= right; c++){if (targetGrid[r][c] != x){vNeiBo[x].emplace(targetGrid[r][c]);}}}}CMyTopSort topSort;topSort.Init(vNeiBo);return 61 == topSort.m_iCount;}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<vector<int>> targetGrid;{Solution sln;targetGrid = { {1,1,1,1},{1,2,2,1},{1,2,2,1},{1,1,1,1} };auto res = sln.isPrintable(targetGrid);Assert(true, res);}{Solution sln;targetGrid = { {1,1,1,1},{1,1,3,3},{1,1,3,4},{5,5,1,4} };auto res = sln.isPrintable(targetGrid);Assert(true, res);}{Solution sln;targetGrid = { {1,2,1},{2,1,2},{1,2,1} };auto res = sln.isPrintable(targetGrid);Assert(false, res);}{Solution sln;targetGrid = { {1,1,1},{3,1,3} };auto res = sln.isPrintable(targetGrid);Assert(false, res);}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛