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



    map<int,vector<int>> graph;

    bool valid(vector<int>& rect1, vector<int>& rect2, vector<vector<int>>& t, int val1, int val2)
    {
        int x1 = -1;
        int y1 = -1;
        int x2 = -1;
        int y2 = -1;
        int ctr = 0;
        // cout<<val1<<"\n";
        // for(auto x: rect1) cout<<x<<" ";
        // cout<<"\n";
        // cout<<val2<<"\n";
        // for(auto x: rect2) cout<<x<<" ";
        // cout<<"\n";
        if(rect1[1] <= rect2[1] && rect1[0] >= rect2[1])
        {
            if(rect1[0] < rect2[0])
            {
                x1 = rect1[0];
                x2 = rect2[1];
            }
            else
            {
                x1 = rect2[0];
                x2 = rect2[1];
            }
        }
        else if(rect2[1] <= rect1[1] && rect2[0] >= rect1[1])
        {
            if(rect2[0] < rect1[0])
            {
                x1 = rect2[0];
                x2 = rect1[1];
            }
            else
            {
                x1 = rect1[0];
                x2 = rect1[1];
            }
        }
        else if(rect1[0] < rect2[1] || rect2[0] < rect1[1])
        {
            return true;
        }

        ctr++;




        if(rect1[3] <= rect2[3] && rect1[2] >= rect2[3])
        {
            if(rect1[2] < rect2[2])
            {
                y1 = rect1[2];
                y2 = rect2[3];
            }
            else
            {
                y1 = rect2[2];
                y2 = rect2[3];
            }
        }
        else if(rect2[3] <= rect1[3] && rect2[2] >= rect1[3])
        {
            if(rect2[2] < rect1[2])
            {
                y1 = rect2[2];
                y2 = rect1[3];
            }
            else
            {
                y1 = rect1[2];
                y2 = rect1[3];
            }
        }
        else if(rect1[2] < rect2[3] || rect2[2] < rect1[3])
        {
            return true;
        }
        set<int> s;
        if(x1 == -1 || x2 == -1 || y1 == -1 || y2 == -1)
        {
            cout<<x1<<"\n";
            cout<<x2<<"\n";
            cout<<y1<<"\n";
            cout<<y2<<"\n";
            cout<<"ERROR -1\n";
            return false;
        }
        for(int a = x2; a<=x1; a++)
        {
            for(int b = y2; b<=y1; b++)
            {
                s.insert(t[b][a]);
                if(s.find(val1) != s.end() && s.find(val2) != s.end()) 
                {
                    cout<<x1<<" "<<x2<<"\n";
                    cout<<y1<<" "<<y2<<"\n";
                    cout<<val1<<" "<<val2<<"\n";
                    return false;
                }
            }
        }
        if(s.count(val1))
        {
            graph[val2].push_back(val1);
        }
        if(s.count(val2))
        {
            graph[val1].push_back(val2);
        }
        return true;
    }





    bool isPrintable(vector<vector<int>>& t) {

        vector<pair<pair<int,int>, pair<int,int>>> rects;

        map<int, vector<int>> coord;

        for(int i=0; i<t.size(); i++)
        {
            for(int j=0; j<t[0].size(); j++)
            {
                if(coord[t[i][j]].size() == 0)
                {
                    vector<int> v = {j,j,i,i};
                    coord[t[i][j]] = v;
                }
                else
                {
                    coord[t[i][j]][0] = max(j, coord[t[i][j]][0]);
                    coord[t[i][j]][1] = min(j, coord[t[i][j]][1]);
                    coord[t[i][j]][2] = max(i, coord[t[i][j]][2]);
                    coord[t[i][j]][3] = min(i, coord[t[i][j]][3]);
                }
            }
        }


        for(auto &i: coord)
        {
            for(auto &j: coord)
            {
                if(i.first!=j.first)
                {
                    if(!valid(i.second, j.second, t, i.first, j.first)) return false;
                }
            }
        }


        map<int, int> indeg;
        set<int> total;
        for(auto it: graph)
        {
            total.insert(it.first);
            for(auto x: it.second)
            {
                indeg[x]++;
                total.insert(x);
            }
        }
        set<int> topo;
        queue<int> q;
        for(auto it: total)
        {
            if(indeg[it] == 0)
            {
                q.push(it);
            }
        }

        while(!q.empty())
        {
            int node= q.front();
            topo.insert(node);
            q.pop();

            for(auto it: graph[node])
            {
                if(indeg[it] == 1)
                {
                    indeg[it] = 0;
                    q.push(it);
                }
                else
                {
                    indeg[it]--;
                }
            }
        }

        if(topo.size() == total.size()) return true;
        return false;










        return true;
        
    }
};
21316