本文涉及的知识点
逆向思考 拓扑排序
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
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。