leetcode做题笔记2132. 用邮票贴满网格图

本文主要是介绍leetcode做题笔记2132. 用邮票贴满网格图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。

思路一：差分数组

c++解法

class Solution {
public:bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {int n = grid.size(),m = grid[0].size();vector<vector<int>> pre(n+3,vector<int>(m+3,0));vector<vector<int>> dif(n+3,vector<int>(m+3,0));for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){pre[i+1][j+1] = pre[i][j+1]+pre[i+1][j]-pre[i][j]+grid[i][j];}}for(int i = 1;i+stampHeight-1<=n;i++){for(int j = 1;j+stampWidth-1<=m;j++){int nx = i+stampHeight-1,ny = j+stampWidth-1;if(pre[nx][ny]-pre[i-1][ny]-pre[nx][j-1]+pre[i-1][j-1]==0){dif[i][j]++;dif[nx+1][j]--;dif[i][ny+1]--;dif[nx+1][ny+1]++;}}}for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){dif[i][j] += dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];if(!grid[i-1][j-1]&&!dif[i][j]) return false;}}return true;}
};

这篇关于leetcode做题笔记2132. 用邮票贴满网格图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---