Krammer's blog

https://leetcode.com/problems/strange-printer-ii/ from Google

We usually need to think backwardly for this kind problem. Hard to think about using DFS to find cycles. I was trying to use greedy but failed. There is a greedy solution in Discussion but looks like the time complexity is O(60^4), which is very likely to get a TLE. Finally I found someone mentioned these very simple steps

Get boundary of each color
For each color, in the boudary, if there’s another color, that means we have a dependency, so we need to remove all dependencies before we can remove ourself
Find if there’s any cycle

這題我在比賽的時候沒解出來，一開始用greedy的解法但太多corner case了，最後解不出來。看了一下討論區發現用確認cycle的方式就可以解了，主要就下列幾步

先算出各個color的上下左右邊界
對於每種顏色，我們把他包含的矩形掃一遍，裡面如果有其他顏色，那就代表我們要移掉這個顏色前必須先移掉其他顏色
最後就很簡單，只要確認這種依賴關係沒有cycle，這題目就可以解

 1class Solution {
 2public:
 3    bool hasCycle(int i, set<int>& path, set<int>& vis, vector<set<int>>& edges) {
 4        if (path.count(i)) return true;
 5        path.insert(i);
 6        for(auto nxt : edges[i]) {
 7            if (vis.count(nxt) == 0) {
 8                if (hasCycle(nxt, path, vis, edges)) return true;
 9            }
10        }
11        path.erase(i);
12        vis.insert(i);
13        return false;
14    }
15    bool isPrintable(vector<vector<int>>& t) {
16        int R = t.size();
17        int C = t[0].size();
18        // boundary of up right bottom left
19        vector<vector<int>> boundary(65, vector<int>(4, -1));
20        for (int i=1; i<=60; i++) boundary[i][0]=65, boundary[i][3]=65;
21        for (int i=0; i<R; i++) {
22            for (int j=0; j<C; j++) {
23                int c = t[i][j];
24                boundary[c][0] = min(boundary[c][0], i);
25                boundary[c][1] = max(boundary[c][1], j);
26                boundary[c][2] = max(boundary[c][2], i);
27                boundary[c][3] = min(boundary[c][3], j);
28            }
29        }
30        vector<set<int>> edges(65);
31        for (int c=1; c<=60; c++) {
32            if (boundary[c][0] == -1) continue;
33            for (int i=boundary[c][0]; i<=boundary[c][2]; i++) {
34                for (int j=boundary[c][3]; j<=boundary[c][1]; j++) {
35                    if (t[i][j] != c) {
36                        edges[t[i][j]].insert(c);
37                    }
38                }
39            }
40        }
41        set<int> vis;
42        for (int i=0; i<=60; i++) {
43            if (vis.count(i) == 0) {
44                set<int> path;
45                if (hasCycle(i, path, vis, edges)) {
46                    return false;
47                }
48            }
49        }
50        return true;
51    }
52};

Editorial: LeetCode 1591 Strange Printer II