<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>>& grid) {
        unordered_set<int> st; // To keep track of all distinct colors in the grid
        map<int, vector<int>> row, col; // To store the starting and ending row and column for each color
        int n = grid.size(), m = grid[0].size();
		
        // Finding all distinct colors in the grid
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                st.insert(grid[i][j]); // Insert each color into the set
        }

		// Finding the bounding box (coordinates) for each color
        for (auto it : st) {
            int mn1 = max(n, m), mn2 = max(m, n), mx1 = 0, mx2 = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == it) { // If the current cell matches the color
                        // Update the bounding box (top-left and bottom-right corners)
                        mn1 = min(i, mn1); // Top row
                        mx1 = max(i, mx1); // Bottom row
                        mn2 = min(j, mn2); // Left column
                        mx2 = max(j, mx2); // Right column
                    }
                }
            }
            row[it].push_back(mn1); // Store the top row
            row[it].push_back(mx1); // Store the bottom row
            col[it].push_back(mn2); // Store the left column
            col[it].push_back(mx2); // Store the right column
        }

		// Now we have the starting and ending coordinates for each color

		// To track dependencies between colors (colors that overlap)
        vector<vector<int>> graph(61, vector<int>()); // Graph for dependencies, max 61 colors
        int indeg[61]; // To store in-degrees of each color (number of dependencies)
        memset(indeg, 0, sizeof indeg); // Initialize in-degrees to 0

        // Building the dependency graph
        for (auto it : st) { // Iterate through each color
            int mnr = row[it][0], mxr = row[it][1], mnc = col[it][0], mxc = col[it][1]; // Get the bounding box coordinates of the color
            set<int> st2; // Set to store colors that overlap with the current color

            // Check for overlapping colors within the bounding box
            for (int i = mnr; i <= mxr; i++) {
                for (int j = mnc; j <= mxc; j++) {
                    if (it != grid[i][j]) // If the cell's color is different from the current color
                        st2.insert(grid[i][j]); // Add the overlapping color to the set
                }
            }

            indeg[it] += st2.size(); // Update the in-degree of the current color based on the number of overlapping colors

            for (auto pt : st2) // For each overlapping color
                graph[pt].push_back(it); // Add the current color as a dependency for the overlapping color
        }

		// Standard Topological Sort to determine if we can print the grid
        int cnt = 0; // Counter to keep track of how many colors we process
        queue<int> q; // Queue for BFS in topological sorting

        // Enqueue all colors with in-degree 0 (no dependencies)
        for (int i = 1; i <= 61; i++) {
            if (st.find(i) != st.end() && indeg[i] == 0) { // If the color exists and has no dependencies
                q.push(i); // Add it to the queue
            }
        }

        // Process the queue using BFS
        while (!q.empty()) {
            int x = q.front(); // Get the front color
            q.pop(); // Remove it from the queue
            cnt++; // Increment the processed color count

            for (auto it : graph[x]) { // For each color that depends on the current color
                indeg[it]--; // Decrease its in-degree
                if (indeg[it] == 0) { // If its in-degree becomes 0 (all dependencies resolved)
                    q.push(it); // Add it to the queue
                }
            }
        }

        // If we processed all distinct colors, the grid can be printed, so return true
        if (cnt == st.size()) {
            return true;
        }
        // Otherwise, return false
        return false;
    }
};

29574