<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; 
        map<int,vector<int>>row,col; 
        int n=grid.size(),m=grid[0].size();
		
    
		for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                st.insert(grid[i][j]);
        }
		
        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)
                    {
                        mn1=min(i,mn1);
                        mx1=max(i,mx1);
                        mn2=min(j,mn2);
                        mx2=max(j,mx2);
                    }
                }
            }
            row[it].push_back(mn1);
            row[it].push_back(mx1);
            col[it].push_back(mn2);
            col[it].push_back(mx2);
        }
		
		// for keeping dependency
        vector<vector<int>>graph(61,vector<int>());
        int indeg[61];
        memset(indeg,0,sizeof indeg);
        for(auto it:st)
        {
            int mnr=row[it][0],mxr=row[it][1],mnc=col[it][0],mxc=col[it][1];
            set<int>st2;
            for(int i=mnr;i<=mxr;i++)
            {
                for(int j=mnc;j<=mxc;j++)
                {
                    if(it!=grid[i][j])
                        st2.insert(grid[i][j]);
                }
            }
            indeg[it]+=st2.size();
            for(auto pt:st2)
                graph[pt].push_back(it);
        }
		
		// Standard Topological Sort 
        int cnt=0;
        queue<int>q;
        for(int i=1;i<=61;i++)
        {
            if(st.find(i)!=st.end() and indeg[i]==0)
                q.push(i);
        }
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            cnt++;
            for(auto it:graph[x])
            {
                indeg[it]--;
                if(indeg[it]==0)
                    q.push(it);
            }
        }
        if(cnt==st.size())
            return true;
        return false;
        
        
    }
};
29574