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

struct Cell {
    int i, j;
};

class Solution {
    const vector<int> di {1, -1, 0, 0};
    const vector<int> dj {0, 0, 1, -1};
    int m, n;
    unordered_map<int, pair<Cell,Cell>> corners;
    unordered_set<int> allColors;
    
    unordered_map<int, pair<Cell, Cell>> getCorners(vector<vector<int>>& grid) {
        unordered_map<int, pair<Cell,Cell>> corners;
        for(int i{}; i < m; ++i) {
            for(int j{}; j < n; ++j) {
                int color = grid[i][j];
                allColors.insert(color);                

                // Handling min since default pair values are 0.
                if(corners.find(color) == corners.end()) {
                    corners[color].first.i = i;
                    corners[color].first.j = j;
                }
                else {
                    corners[color].first.i = min(corners[color].first.i, i);
                    corners[color].first.j = min(corners[color].first.j, j);
                }

                corners[color].second.i = max(corners[color].second.i, i);
                corners[color].second.j = max(corners[color].second.j, j);

                // if(color==4 || color==5) {
                //     cout << color << ": " << corners[color].first.i << " " << corners[color].first.j << endl;
                //     cout << color << ": " << corners[color].second.i << " " << corners[color].second.j << endl;
                // }
            }
        }
        return corners;
    }

    bool isFullRec(int color, vector<vector<int>>& grid) {
        auto corner1 = corners[color].first;
        auto corner2 = corners[color].second;

        int maxI = corner2.i;
        int maxJ = corner2.j;
        for(int i = corner1.i; i <= maxI; i++)
            for(int j = corner1.j; j <= maxJ; j++) {
                if(grid[i][j] != color) {
                    return false;
                }
            }
        return true;
    }

    bool isCellInsideColor(pair<Cell, Cell> color, Cell cell) {
        return (cell.i >= color.first.i && cell.j >= color.first.j) && 
               (cell.i <= color.second.i && cell.j <= color.second.j);
    }
    bool isInside(pair<Cell, Cell> color1, pair<Cell, Cell> color2) {
        return isCellInsideColor(color1, color2.first) || isCellInsideColor(color1, color2.second);
    }
    bool valid(Cell cell, pair<Cell, Cell> corner) {
        int minI = corner.first.i;
        int minJ = corner.first.j;
        int maxI = corner.second.i;
        int maxJ = corner.second.j;

        return (cell.i >= 0 && cell.i < m) && (cell.j >= 0 && cell.j < n) &&
               (cell.i >= minI && cell.i <= maxI) && (cell.j >= minJ && cell.j <= maxJ);
    }
    void coloring(Cell cell, int& color, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
        int i {cell.i};
        int j {cell.j};
        
        visited[i][j] = true;
        grid[i][j] = color;
        
        for(int d{}; d < 4; ++d) {
            int i2 = i + di[d];
            int j2 = j + dj[d];

            if(valid({i2, j2}, corners[color]) && !visited[i2][j2]) {
                coloring({i2, j2}, color, grid, visited);
            }
        }
    }
    void printGrid(vector<vector<int>>& newGrid) {
        cout << "== THE GRID ==\n";
        for(int i{}; i < m; ++i) {
            for(int j{}; j < n; ++j) {
                cout << newGrid[i][j] << " ";
            }
            cout << endl;
        }
        cout << "== END OF GRID ==\n";
    }
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {
        m = targetGrid.size();
        n = targetGrid.front().size();
        corners = getCorners(targetGrid);
        
        unordered_map<int, unordered_set<int>> adjacent;
        unordered_map<int, int> inDegree;
        
        for(auto p1 : corners) {
            int color = p1.first;
            auto corner1 = p1.second.first;
            auto corner2 = p1.second.second;

            int maxI = corner2.i;
            int maxJ = corner2.j;
            for(int i = corner1.i; i <= maxI; i++)
                for(int j = corner1.j; j <= maxJ; j++) {
                    if(targetGrid[i][j] != color) {
                        
                        if(adjacent[color].insert(targetGrid[i][j]).second) {
                            cout << color << " --> " << targetGrid[i][j] << endl;
                            inDegree[targetGrid[i][j]]++;
                        }
                    }
                }
        }

        queue<int> colors;
        for(auto color : allColors) {
            if(!inDegree[color]) {
                colors.push(color);
            }
        }
        
        cout << "Queue Size: " << colors.size() << endl;

        vector<vector<int>> newGrid(m, vector<int>(n));
        while(!colors.empty()) {
            int size = colors.size();
            while(size--) {
                int current = colors.front();
                colors.pop();

                Cell upperLeft = corners[current].first;
                vector<vector<bool>> visited(m, vector<bool>(n));
                // cout << "CAlLING COLORING. . ." << endl;
                coloring(upperLeft, current, newGrid, visited);
                
                for(auto child : adjacent[current]) {
                    if(!--inDegree[child]) {
                        colors.push(child);
                    }
                }
            }
        }

        printGrid(newGrid);
        // Check if the newGrid is different from targetGrid
        for(int i{}; i < m; ++i) {
            for(int j{}; j< n; ++j) {
                if(newGrid[i][j] != targetGrid[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
};
31409