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
Solution: Dependency graph
For each color C find the maximum rectangle to cover it. Any other color C’ in this rectangle is a dependency of C, e.g. C’ must be print first in order to print C.
Then this problem reduced to check if there is any cycle in the dependency graph.
e.g.
1 2 1
2 1 2
1 2 1
The maximum rectangle for 1 and 2 are both [0, 0] ~ [2, 2]. 1 depends on 2, and 2 depends on 1. This is a circular reference and no way to print.
Time complexity: O(C*M*N)
Space complexity: O(C*C)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public: bool isPrintable(vector<vector<int>>& targetGrid) { constexpr int kMaxC = 60; const int m = targetGrid.size(); const int n = targetGrid[0].size(); vector<unordered_set<int>> deps(kMaxC + 1); for (int c = 1; c <= kMaxC; ++c) { int l = n, r = -1, t = m, b = -1; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (targetGrid[i][j] == c) l = min(l, j), r = max(r, j), t = min(t, i), b = max(b, i); if (l == -1) continue; for (int i = t; i <= b; ++i) for (int j = l; j <= r; ++j) if (targetGrid[i][j] != c) deps[c].insert(targetGrid[i][j]); } vector<int> seen(kMaxC + 1); function<bool(int)> hasCycle = [&](int c) { if (seen[c] == 1) return true; if (seen[c] == 2) return false; seen[c] = 1; for (int t : deps[c]) if (hasCycle(t)) return true; seen[c] = 2; return false; }; for (int c = 1; c <= kMaxC; ++c) if (hasCycle(c)) return false; return true; } }; |