1
class Solution {
2
 public:
3
  bool possibleToStamp(vector<vector<int>> &grid, int stampHeight, int stampWidth) {
4
    h = stampHeight;
5
    w = stampWidth;
6
    init(grid);
7

8
    vector<vector<int>> diff(m + 1, vector<int>(n + 1, 0)); // 1-indexed
9
    for (int i = m - 1; i >= 0; i--) {
10
      for (int j = n - 1; j >= 0; j--) {
11
        if (canStamp(i, j)) {
12
          diff[i + 1][j + 1]++;
13
          diff[i + 1][j + 1 - w]--;
14
          diff[i + 1 - h][j + 1]--;
15
          diff[i + 1 - h][j + 1 - w]++;
16
        }
17
      }
18
    }
19
    int cur = 0;
20
    for (int i = m - 1; i >= 0; i--) {
21
      if (i < m - 1) {
22
        for (int j = 0; j <= n; j++) diff[i + 1][j] += diff[i + 2][j];
23
      }
24
      for (int j = n - 1; j >= 0; j--) {
25
        cur += diff[i + 1][j + 1];
26
        if (cur > 0) {
27
          grid[i][j] = 1;
28
        }
29
      }
30
      cur += diff[i + 1][0];
31
    }
32

33
    for (int i = 0; i < m; i++) {
34
      for (int j = 0; j < n; j++) {
35
        if (grid[i][j] != 1) return false;
36
      }
37
    }
38

39
    return true;
40
  }
41

42
 private:
43
  vector<vector<int>> pre;
44
  int h;
45
  int w;
46
  int m;
47
  int n;
48
  void init(vector<vector<int>> &grid) {
49
    m = grid.size(), n = grid[0].size();
50
    // initialize prefix sum
51
    pre.resize(m + 1, vector<int>(n + 1, 0)); // 1-indexed
52
    for (int i = 0; i < m; i++) {
53
      for (int j = 0; j < n; j++) {
54
        pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + grid[i][j];
55
      }
56
    }
57
  }
58
  bool canStamp(int i, int j) {
59
    if (i + 1 < h || j + 1 < w) return false;
60
    return pre[i + 1][j + 1] - pre[i + 1][j + 1 - w] - pre[i + 1 - h][j + 1] +
61
               pre[i + 1 - h][j + 1 - w] ==
62
           0;
63
  }
64
};