<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 Node{
    public:
    int l,r,u,d;

    Node(int a,int b,int c,int dow){
        l=a;
        r=b;
        u=c;
        d=dow;
    }
};
class Solution {
public:
// store the rectangle of each number and also store the numbers present in the reactangle of that number 
// now for every number go to all the numbers present in its recatngle and then check that current number should not be present 
// inside the rectangle of any of those numbers 
    Node* findrec(int no,vector<vector<int>>& grid)
    {
        int n=grid.size(),m=grid[0].size();
        int l=m,r=-1,u=n,d=-1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==no) {
                    l=min(l,j);
                    r=max(r,j);
                    u=min(u,i);
                    d=max(d,i);
                }
            }
        }
        return new Node(l,r,u,d);
    }
    vector<int> allnum(int l,int r,int u,int d,vector<vector<int>>& grid){
        vector<int> freq(61,0);
        for(int i=l;i<=r;i++)
        {
            for(int j=u;j<=d;j++)
            {
                freq[grid[j][i]]=1;
            }
        }
        return freq;
    }
    //a cycle can be detected in a directed graph using dfs 
    bool detectcycle(int node,vector<vector<int>>& adj,vector<int>& vis,vector<int>& curr_vis){
        // vector<int> vis(60,0);
        vis[node]=1;
        curr_vis[node]=1;
        bool ans=0;
        for(auto x: adj[node]){
            if(curr_vis[x]) return 1;
            else if(!curr_vis[x] && !vis[x]) {
                // if(vis[x])
                ans=ans|detectcycle(x,adj,vis,curr_vis);
                // if(detectcyle)
            }
        }
        curr_vis[node]=0;
        return ans;
    }
    bool isPrintable(vector<vector<int>>& targetGrid) {
        vector<Node*> rectangles;
        rectangles.push_back(new Node(targetGrid[0].size(),-1,targetGrid.size(),-1));
        vector<vector<int>> numbers;
        for(int i=1;i<=60;i++) rectangles.push_back(findrec(i,targetGrid));
        numbers.push_back({});
        for(int i=1;i<=60;i++){
            numbers.push_back(allnum(rectangles[i]->l,rectangles[i]->r,rectangles[i]->u,rectangles[i]->d,targetGrid));
        }
        // for(int i=1;i<=60;i++){
        //     cout<<rectangles[i]->l<<rectangles[i]->r<<rectangles[i]->u<<rectangles[i]->d<<endl;
        // }
        // for(int i=1;i<=60;i++){
        //     if(rectangles[i]->r!=-1) {
        //         cout<<i<<" ";
        //         for(auto x: numbers[i]) cout<<x<<" ";
        //         cout<<endl;
        //     }
        // }
        // for(int i=1;i<=60;i++)
        // {
        //     for(int j=1;j<=60;j++)
        //     {
        //         if(i!=j && numbers[i][j])
        //         {
        //             if(numbers[j][i]) return 0;
        //         }
        //     }
        // }
        vector<vector<int>> adj(61);
        for(int i=1;i<=60;i++){
            // vector<int> vec;
            for(int j=1;j<=60;j++)
            {
                if(j!=i && numbers[i][j]) adj[i].push_back(j); 
            }
            // adj
        }
        for(int i=0;i<61;i++){
        for(auto x: adj[i]) cout<<x<<" ";
        cout<<endl;
        }
        vector<int> vis(61,0);
        for(int i=1;i<=60;i++)
        {
            if(!vis[i]){
                vector<int> curr_vis(61,0);
                if(detectcycle(i,adj,vis,curr_vis)) return false;
            }
        }

        return 1;
    }
};
25445