Formatted question description: https://leetcode.ca/all/1591.html

1591. Strange Printer II (Hard)

There is a strange printer with the following two special requirements:

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.
Once the printer has used a color for the above operation, the same color cannot be used again.

You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true

Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true

Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.

Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

Constraints:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

Related Topics:
Greedy

Similar Questions:

Strange Printer (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/strange-printer-ii/

// Time: O(C^2 * MN)
// Space: O(MN)
class Solution {
    bool removable(vector<vector<int>> &G, vector<vector<int>> &pos, int c) {
        for (int i = pos[c][0]; i <= pos[c][2]; ++i) {
            for (int j = pos[c][1]; j <= pos[c][3]; ++j) {
                if (G[i][j] != c && G[i][j] != 0) return false;
            }
        }
        for (int i = pos[c][0]; i <= pos[c][2]; ++i) {
            for (int j = pos[c][1]; j <= pos[c][3]; ++j) G[i][j] = 0;
        }
        return true;
    }
public:
    bool isPrintable(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size();
        vector<vector<int>> pos(61, {M, N, 0, 0});
        unordered_set<int> colors, remove;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                int c = G[i][j];
                colors.insert(c);
                pos[c][0] = min(pos[c][0], i);
                pos[c][1] = min(pos[c][1], j);
                pos[c][2] = max(pos[c][2], i);
                pos[c][3] = max(pos[c][3], j);
            }
        }
        while (colors.size()) {
            for (int c : colors) {
                if (removable(G, pos, c)) remove.insert(c);
            }
            if (remove.empty()) return false;
            for (int c : remove) colors.erase(c);
            remove.clear();
        }
        return true;
    }
};

Solution 2. Topological Sort

// OJ: https://leetcode.com/problems/strange-printer-ii/

// Time: O(CMN + C^2)
// Space: O(C^2)
class Solution {
    bool hasCircle(int c, unordered_map<int, unordered_set<int>> &dep, vector<int> &state) {
        if (state[c] != -1) return !state[c];
        state[c] = 0;
        for (int d : dep[c]) {
            if (state[d] == 1) continue;
            if (state[d] == 0) return true;
            if (hasCircle(d, dep, state)) return true;
        }
        state[c] = 1;
        return false;
    }
public:
    bool isPrintable(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size();
        unordered_set<int> colors;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) colors.insert(G[i][j]);
        }
        unordered_map<int, unordered_set<int>> dep(61); // dependency graph: If dep[i] contains j, then color j covers color i.
        for (int i : colors) {
            int minx = M, miny = N, maxx = -1, maxy = -1;
            for (int x = 0; x < M; ++x) {
                for (int y = 0; y < N; ++y) {
                    if (G[x][y] != i) continue;
                    minx = min(minx, x);
                    miny = min(miny, y);
                    maxx = max(maxx, x);
                    maxy = max(maxy, y);
                }
            }
            for (int x = minx; x <= maxx; ++x) {
                for (int y = miny; y <= maxy; ++y) {
                    if (G[x][y] != i) dep[i].insert(G[x][y]);
                }
            }
        }
        vector<int> state(61, -1); // -1 unvisited, 0 visiting, 1 visited
        for (int i : colors) {
            if (hasCircle(i, dep, state)) return false;
        }
        return true;
    }
};

Java

class Solution {
    public boolean isPrintable(int[][] targetGrid) {
        Map<Integer, int[]> boundsMap = new HashMap<Integer, int[]>();
        int rows = targetGrid.length, columns = targetGrid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                int color = targetGrid[i][j];
                if (!boundsMap.containsKey(color))
                    boundsMap.put(color, new int[]{i, i, j, j});
                else {
                    int[] bounds = boundsMap.get(color);
                    bounds[0] = Math.min(bounds[0], i);
                    bounds[1] = Math.max(bounds[1], i);
                    bounds[2] = Math.min(bounds[2], j);
                    bounds[3] = Math.max(bounds[3], j);
                    boundsMap.put(color, bounds);
                }
            }
        }
        Set<Integer> keySet = boundsMap.keySet();
        Map<Integer, List<Integer>> greaterMap = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                int color = targetGrid[i][j];
                List<Integer> list = greaterMap.getOrDefault(color, new ArrayList<Integer>());
                for (int key : keySet) {
                    if (key != color) {
                        int[] bounds = boundsMap.get(key);
                        if (i >= bounds[0] && i <= bounds[1] && j >= bounds[2] && j <= bounds[3])
                            list.add(key);
                    }
                }
                greaterMap.put(color, list);
            }
        }
        Map<Integer, Integer> indegreeMap = new HashMap<Integer, Integer>();
        for (int color : keySet) {
            List<Integer> nextColors = greaterMap.getOrDefault(color, new ArrayList<Integer>());
            for (int nextColor : nextColors) {
                int indegree = indegreeMap.getOrDefault(nextColor, 0) + 1;
                indegreeMap.put(nextColor, indegree);
            }
        }
        Set<Integer> visited = new HashSet<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int color : keySet) {
            int indegree = indegreeMap.getOrDefault(color, 0);
            if (indegree == 0) {
                visited.add(color);
                queue.offer(color);
            }
        }
        while (!queue.isEmpty()) {
            int color = queue.poll();
            List<Integer> nextColors = greaterMap.getOrDefault(color, new ArrayList<Integer>());
            for (int nextColor : nextColors) {
                int indegree = indegreeMap.getOrDefault(nextColor, 0) - 1;
                if (indegree == 0) {
                    indegreeMap.remove(nextColor);
                    visited.add(nextColor);
                    queue.offer(nextColor);
                } else
                    indegreeMap.put(nextColor, indegree);
            }
        }
        return visited.size() == keySet.size();
    }
}

// OJ: https://leetcode.com/problems/strange-printer-ii/
// Time: O(C^2 * MN)
// Space: O(MN)
class Solution {
    bool removable(vector<vector<int>> &G, vector<vector<int>> &pos, int c) {
        for (int i = pos[c][0]; i <= pos[c][2]; ++i) {
            for (int j = pos[c][1]; j <= pos[c][3]; ++j) {
                if (G[i][j] != c && G[i][j] != 0) return false;
            }
        }
        for (int i = pos[c][0]; i <= pos[c][2]; ++i) {
            for (int j = pos[c][1]; j <= pos[c][3]; ++j) G[i][j] = 0;
        }
        return true;
    }
public:
    bool isPrintable(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size();
        vector<vector<int>> pos(61, {M, N, 0, 0});
        unordered_set<int> colors, remove;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                int c = G[i][j];
                colors.insert(c);
                pos[c][0] = min(pos[c][0], i);
                pos[c][1] = min(pos[c][1], j);
                pos[c][2] = max(pos[c][2], i);
                pos[c][3] = max(pos[c][3], j);
            }
        }
        while (colors.size()) {
            for (int c : colors) {
                if (removable(G, pos, c)) remove.insert(c);
            }
            if (remove.empty()) return false;
            for (int c : remove) colors.erase(c);
            remove.clear();
        }
        return true;
    }
};

```
print("Todo!")
```

1591 - Strange Printer II

1591. Strange Printer II (Hard)

Solution 1.

Solution 2. Topological Sort

All Problems

All Solutions