<p>There is a strange printer with the following two special requirements:</p>

<ul>
	<li>On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.</li>
	<li>Once the printer has used a color for the above operation, <strong>the same color cannot be used again</strong>.</li>
</ul>

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

<p>Return <code>true</code><em> if it is possible to print the matrix </em><code>targetGrid</code><em>,</em><em> otherwise, return </em><code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/23/print1.jpg" style="width: 600px; height: 175px;" />
<pre>
<strong>Input:</strong> targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/23/print2.jpg" style="width: 600px; height: 367px;" />
<pre>
<strong>Input:</strong> targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == targetGrid.length</code></li>
	<li><code>n == targetGrid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 60</code></li>
	<li><code>1 &lt;= targetGrid[row][col] &lt;= 60</code></li>
</ul>

enum class State { kInit, kVisiting, kVisited };

class Solution {
 public:
  bool isPrintable(vector<vector<int>>& targetGrid) {
    constexpr int kMaxColor = 60;
    const int m = targetGrid.size();
    const int n = targetGrid[0].size();
    // graph[u] := {v1, v2} means v1 and v2 cover u
    vector<unordered_set<int>> graph(kMaxColor + 1);

    for (int color = 1; color <= kMaxColor; ++color) {
      // Get the rectangle of the current color.
      int minI = m;
      int minJ = n;
      int maxI = -1;
      int maxJ = -1;
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
          if (targetGrid[i][j] == color) {
            minI = min(minI, i);
            minJ = min(minJ, j);
            maxI = max(maxI, i);
            maxJ = max(maxJ, j);
          }
      // Add any color covering the current as the children.
      for (int i = minI; i <= maxI; ++i)
        for (int j = minJ; j <= maxJ; ++j)
          if (targetGrid[i][j] != color)
            graph[color].insert(targetGrid[i][j]);
    }

    vector<State> states(kMaxColor + 1);

    for (int color = 1; color <= kMaxColor; ++color)
      if (hasCycle(graph, color, states))
        return false;

    return true;
  }

 private:
  bool hasCycle(const vector<unordered_set<int>>& graph, int u,
                vector<State>& states) {
    if (states[u] == State::kVisiting)
      return true;
    if (states[u] == State::kVisited)
      return false;

    states[u] = State::kVisiting;
    for (const int v : graph[u])
      if (hasCycle(graph, v, states))
        return true;
    states[u] = State::kVisited;

    return false;
  }
};
24986