1
class Solution {
2
  struct Bounds {
3
    int left, right, top, bottom;
4
    Bounds() : left(INT_MAX), right(INT_MIN), top(INT_MAX), bottom(INT_MIN) {}
5
  };
6
  unordered_map<int, Bounds> colors;
7

8
  bool cycle(vector<vector<int>> &grid, int col) {
9
    for (int i = colors[col].top; i <= colors[col].bottom; ++i) {
10
      for (int j = colors[col].left; j <= colors[col].right; ++j) {
11
        if (grid[i][j] == -1)
12
          return true; // already visited and unresolved!
13
        else if (grid[i][j] == col)
14
          grid[i][j] = -1; // mark visiting
15
        else if (grid[i][j] && cycle(grid, grid[i][j]))
16
          return true;
17
      }
18
    }
19

20
    for (int i = colors[col].top; i <= colors[col].bottom; ++i) {
21
      for (int j = colors[col].left; j <= colors[col].right; ++j) {
22
        grid[i][j] = 0; // resolved
23
      }
24
    }
25

26
    return false;
27
  }
28

29
 public:
30
  bool isPrintable(vector<vector<int>> &targetGrid) {
31
    for (int i = 0; i < targetGrid.size(); ++i) {
32
      for (int j = 0; j < targetGrid[0].size(); ++j) {
33
        colors[targetGrid[i][j]].left = min(colors[targetGrid[i][j]].left, j);
34
        colors[targetGrid[i][j]].top = min(colors[targetGrid[i][j]].top, i);
35
        colors[targetGrid[i][j]].right = max(colors[targetGrid[i][j]].right, j);
36
        colors[targetGrid[i][j]].bottom = max(colors[targetGrid[i][j]].bottom, i);
37
      }
38
    }
39

40
    for (int i = 0; i < targetGrid.size(); ++i) {
41
      for (int j = 0; j < targetGrid[0].size(); ++j) {
42
        if (targetGrid[i][j] && cycle(targetGrid, targetGrid[i][j])) return false;
43
      }
44
    }
45

46
    return true;
47
  }
48
};