<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>

class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        unordered_map<int, unordered_set<int>> adjList;
        unordered_map<int, vector<int> > regions; // top, bottom, left, right
        int n = targetGrid.size();
        int m = targetGrid[0].size();
        if (n == 1 && m == 1)
            return true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int color = targetGrid[i][j];
                if (!adjList.count(color))
                    adjList[color];
                if (!regions.count(color)) {
                    regions[color] = {i, i, j, j};
                } else {
                    regions[color][0] = min(i, regions[color][0]);
                    regions[color][1] = max(i, regions[color][1]);
                    regions[color][2] = min(j, regions[color][2]);
                    regions[color][3] = max(j, regions[color][3]);
                }
                
            }
        }
        for (auto &[color, intersects] : adjList) {
            for (int i = regions[color][0]; i <= regions[color][1]; i++) {
                for (int j = regions[color][2]; j <= regions[color][3]; j++) {
                    int cellColor = targetGrid[i][j];
                    if (cellColor != color) {
                        intersects.insert(cellColor);
                        // cout << "color " << color << " contains " << cellColor << endl;
                    }
                }
            }
        }

        unordered_map<int, int> indegree;
        for (auto &[color, intersects] : adjList) {
            indegree[color] = intersects.size();
            // cout << "indegree " << color << " = " << indegree[color] << endl; 
        }
        
        // topological sort
        queue<int> q;
        for (auto &[color, degrees] : indegree)
            if (degrees == 0) {
                q.push(color);
            }
        if (q.empty())
            return false;
        while (q.size()) {
            int color = q.front();
            q.pop();
            // cout << "processing color " << color << endl;
            for (auto &[neighbourColor, intersects] : adjList) {
                if (intersects.count(color))
                    if (--indegree[neighbourColor] == 0)
                        q.push(neighbourColor);
            }
            // for (auto &neighbourColor : adjList[color]) {
            //     if (--indegree[neighbourColor] == 0)
            //         q.push(neighbourColor);
            // }
        }
        for (auto &[color, degrees] : indegree)
            if (degrees != 0)
                return false;
        return true;
    }
};

26363