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

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);
  }
}