【每日一题】用邮票贴满网格图

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：二维前缀和+二维差分
写在最后

Tag

【二维前缀和】【二维差分】【矩阵】【2023-12-14】

题目来源

2132. 用邮票贴满网格图

题目解读

在 01 矩阵中，判断是否可以用给定尺寸的邮票将所有 0 位置都覆盖住，邮票之间可以重叠但是不能超出矩阵的的边缘。如果可以返回 true，否则返回 false。

解题思路

方法一：二维前缀和+二维差分

思路

我们贪心的进行覆盖，只要有足够大的空格（邮票尺寸那么大没被占据的）的地方，我们就用邮票来覆盖。记录空格被多少张邮票覆盖了，如果最后存在空格子没被覆盖，则返回 false，否则返回 true。

具体流程如下：

枚举邮票尺寸大小的矩形，需要使用二维前缀和判断枚举的区域是否没被占据；
记录空格被多少张邮票覆盖了，使用二维差分记录；
统计是否存在空格子没被覆盖，如是则返回 false，否则返回 true，使用二维差分还原。

二维前缀和

如何判断某个矩形区域可以覆盖邮票？只要该区域内没有被占据就可以，即一个矩形区域的元素和等于 0。为此，我们使用二维前缀和 $O (1)$ 的统计任意矩阵区域的元素和。

这里直接贴出代码，如果对二维前缀和内容不熟悉可以参考一文讲清楚【前缀和】。

vector<vector<int>> preSum2d(m+1, vector<int>(n+1));
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        preSum2d[i+1][j+1] = preSum2d[i][j+1] + preSum2d[i+1][j] - preSum2d[i][j] + grid[i][j];
    }
}

二维差分

实现代码

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> preSum2d(m+1, vector<int>(n+1));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                preSum2d[i+1][j+1] = preSum2d[i][j+1] + preSum2d[i+1][j] - preSum2d[i][j] + grid[i][j];
            }
        }
        
        vector<vector<int>> diff(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;
                if (preSum2d[i2][j2] - preSum2d[i2][j1-1] - preSum2d[i1-1][j2] + preSum2d[i1-1][j1-1] == 0) {
                    diff[i1][j1] ++;
                    diff[i1][j2+1] --;
                    diff[i2+1][j1] --;
                    diff[i2+1][j2+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] == 0 && diff[i+1][j+1] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
};