力扣2132.用邮票贴满网格图

力扣2132.用邮票贴满网格图

• 二维差分 + 二维前缀和

  • 对于一个可以贴邮票的矩阵，其和一定为0
  • 通过前缀和可以求出任意一个矩阵的和，为0时贴上邮票
  • 贴上邮票即为在矩阵+1，可以用二维差分实现
  • 最后差分求和，若一个格子grid[i][j] == 0 && sum == 0则没有全覆盖

•   class Solution {
    public:
        bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
            int m = grid.size(),n = grid[0].size();
            //求前缀和
            vector<vector<int>> s(m+1,vector<int>(n+1));
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                    s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + grid[i][j];
            //求差分数组
            vector<vector<int>> d(m+2,vector<int>(n+2));
            for(int i2=stampHeight;i2<=m;i2++)
            {
                for(int j2=stampWidth;j2<=n;j2++)
                {
                    //左上角坐标
                    int i1 = i2 - stampHeight + 1;
                    int j1 = j2 - stampWidth + 1;
                    //这个矩阵全为0，可以贴邮票
                    if(s[i2][j2] - s[i2][j1-1] - s[i1-1][j2] + s[i1-1][j1-1] == 0)
                    {
                        d[i1][j1] ++;
                        d[i1][j2+1] --;
                        d[i2+1][j1] --;
                        d[i2+1][j2+1] ++;
                    }
                }
            }
            //复原差分数组
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                {
                    d[i+1][j+1] += d[i+1][j] + d[i][j+1] - d[i][j];
                    //应该贴但是没贴
                    if(grid[i][j] == 0 && d[i+1][j+1] == 0)
                        return false;
                }
            return true;
        }
    };