LeetCode 2132. 用邮票贴满网格图

一、题目

1、题目描述

给你一个?m x n?的二进制矩阵?grid?，每个格子要么为?0?（空）要么为?1?（被占据）。

给你邮票的尺寸为?stampHeight x stampWidth?。我们想将邮票贴进二进制矩阵中，且满足以下?限制?和?要求?：

1. 覆盖所有?空?格子。
2. 不覆盖任何?被占据?的格子。
3. 我们可以放入任意数目的邮票。
4. 邮票可以相互有?重叠?部分。
5. 邮票不允许?旋转?。
6. 邮票必须完全在矩阵?内?。

如果在满足上述要求的前提下，可以放入邮票，请返回?true?，否则返回?false?。

2、接口描述

?

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        
    }
};

3、原题链接

2132. 用邮票贴满网格图

---

二、解题报告

1、思路分析

对于邮票能够合法覆盖的区域内的方格[i,j]，一定满足如下条件：

1、[i,j]为长度大于等于stampWidth的全0行子序列的一格

2、[i,j]为长度大于等于stampHeight的全0列子序列的一格

我们可以对每个格子满足条件1、2打上标记，如果所有0方格都被打上标记我们就返回true

注意到：1、2可以转化为一句话

[i,j]为宽度stampWidth高度stampHeight的某个全0子矩阵中的一格

那么对于这样一个矩形，有什么特点？或者说我们怎样快速判断一个高度为为stampHeight宽度为

stampWidth的子矩阵是否满足全0呢？

对于一段一维子序列，我们只要求出区间和就能判断。如果多次判断不同一维子序列，我们可以通过O(n)计算前缀和来O(1)计算任意区间和。

对于二维我们也一样，只要维护二维前缀和即可。

关于前缀和及二维前缀和，见前缀和超干货详解

那么对于一个高度为为stampHeight宽度为stampWidth的子矩阵只要全0，那么该子矩阵内的所有元素都是可覆盖点，也就是说我们遍历所有高度为为stampHeight宽度为stampWidth的子矩阵就能找到所有可覆盖方格！

我们只需要另外开一个矩阵来对可覆盖方格进行标记即可。

那么如何快速标记一个矩阵内的方格呢？

对于快速区间操作，我们有树状数组，线段树，差分数组，这里逻辑简单，只需要用二维差分数组即可。

关于差分数组，见差分数组详解，一维二维差分-CSDN博客

然后对差分数组求二维前缀和，如果存在grid[i][j] = 0并且diff[i + 1][j + 1] = 0（注意diff此时已经求完前缀和了）,那么我们就返回false

2、复杂度

时间复杂度：O(mn)? ? ? ? 空间复杂度：O(mn)

3、代码详解

?

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int m = grid.size() , n = grid[0].size() , x , y;
        vector<vector<int>> diff(m + 2 , vector<int>(n + 2)) , pre(m + 1 , vector<int>(n + 1));
        //prefixsum
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j < n ; j++)
                pre[i + 1][j + 1] = grid[i][j] + pre[i + 1][j] + pre[i][j + 1] - pre[i][j];

        for(int i = stampHeight ; i <= m ; i++)
            for(int j = stampWidth ; j <= n ; j++){
                x = i - stampHeight , y = j - stampWidth;
                //邮票大小内全为0
                if(!(pre[i][j] - pre[i][y] - pre[x][j] + pre[x][y])){
                    diff[x + 1][y + 1]++;
                    diff[i + 1][y + 1]--;
                    diff[x + 1][j + 1]--;
                    diff[i + 1][j + 1]++;
                }
            }
            
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j < n ; j++){
                diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
                if(!grid[i][j] && !diff[i + 1][j + 1]) return false;
            }
        return true;
    }
};