今天做这道题唯一的感觉就是，条件真的多。第一次读了假题，没注意到邮票不能旋转，还说这道题为什么这么难。

其实就是一道很简单的二位前缀和以及差分题

先求一个前缀和可以O（1）查询所有的邮票能不能放下，在所有可以放邮票的位置都放邮票，diff相当于是放邮票的次数的前缀和，最后再用一个前缀和求哪些地方是没有放过邮票的，如果这个点同时不是被占据的那么就不可以。反之返回true。

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
35
class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>>diff(m+2,vector<int>(n+2,0));
        vector<vector<int>>pre(m+2,vector<int>(n+2,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+grid[i-1][j-1];
            }
        }
        for(int i=1;i+h-1<=m;i++){
            for(int j=1;j+w-1<=n;j++){
                int x=i+h-1;
                int y=j+w-1;
                if(pre[x][y]-pre[i-1][y]-pre[x][j-1]+pre[i-1][j-1]==0){
                    diff[i][j]++;
                    diff[i][y+1]--;
                    diff[x+1][j]--;
                    diff[x+1][y+1]++;
                }
            }
        }
        for(inti=1;i<=m;i++) {
            for(int j=1; j<=n;j++) {
                diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
                if (diff[i][j]==0&&grid[i-1][j-1] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
};