<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:
    void dfs ( int node , vector<vector<int>> &adj , stack<int>&st , vector<int> &vis ){
        vis[node] = 1;
        for ( auto e : adj[node] ){
            if ( !vis[e] )dfs ( e , adj , st , vis );
        }
        st.push(node);
    }
    stack<int> topo_sort ( vector<vector<int>> &coord ,  vector<vector<int>> & grid , int c ){
        vector<vector<int>> adj ( c + 1 );
        // vector < int > indegree ( c + 1 ,0 );
        for ( int k = 1 ; k <= c ; k ++ ){
            int mini = coord[k][0] , maxi = coord[k][1] , minj = coord[k][2] , maxj = coord[k][3];
            for ( int i = mini ; i <= maxi ; i ++ ){
                for ( int j = minj ; j <= maxj ; j ++ ){
                    if ( grid[i][j] != k ){
                        //indegree[k] ++;
                        adj[k].push_back ( grid[i][j] );
                    }
                }
            }
        }
        
        vector < int > vis ( c + 1 , 0 );
        stack < int > st;
        for ( int k = 1 ; k <= c ; k ++ ){
            if ( !vis[k] ) dfs ( k , adj , st , vis );
        }
        return st;
    }
    bool isPrintable(vector<vector<int>>& grid) {
        int c = 0;
        int n = grid.size() , m = grid[0].size();
        for ( int i = 0 ; i < n ; i ++ ){
            for ( int j = 0 ; j < m ; j ++ ){
                c = max ( grid[i][j] , c );
            }
        }
        vector<vector<int>> coord ( c + 1 , { n , 0 , m , 0} );
        for ( int i = 0 ; i < n ; i ++ ){
            for ( int j = 0 ; j < m ; j ++ ){
                int curr = grid[i][j];
                coord[curr][0] = min ( coord[curr][0] , i );
                coord[curr][1] = max ( coord[curr][1] , i );
                coord[curr][2] = min ( coord[curr][2] , j );
                coord[curr][3] = max ( coord[curr][3] , j );
            }
        }
        // for ( auto e : coord ){
        //     for ( auto p : e ) cout << p<< " ";
        //     cout << endl;
        // }
        // cout << endl;
        stack<int> st = topo_sort( coord , grid , c );
        vector<vector <int>> matrix ( n , vector <int> ( m ));
        while ( !st.empty() ){
            int k = st.top() ; st.pop();
            int mini = coord[k][0] , maxi = coord[k][1] , minj = coord[k][2] , maxj = coord[k][3];
            if ( mini == 4 && maxi == 0 && minj == 4 && maxj == 0 ) continue;
            for ( int i = mini ; i <= maxi ; i ++ ){
                for ( int j = minj ; j <= maxj ; j ++ ){
                    matrix[i][j] = k;
                }
            }
        }
        // for ( int i = 0 ; i < n ; i ++ ){
        //     for ( int j = 0 ; j < m ; j ++ ){
        //         cout << matrix[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        // cout << endl;
        
        for ( int i = 0 ; i < n ; i ++ ){
            for ( int j = 0 ; j < m ; j ++ ){
                if ( matrix[i][j] != grid[i][j] ) return false;
            }
        }
        return true;
    }
};
45171