leetcode做题笔记2132. 用邮票贴满网格图
2023-12-14 22:37:46
给你一个?m x n
?的二进制矩阵?grid
?,每个格子要么为?0
?(空)要么为?1
?(被占据)。
给你邮票的尺寸为?stampHeight x stampWidth
?。我们想将邮票贴进二进制矩阵中,且满足以下?限制?和?要求?:
- 覆盖所有?空?格子。
- 不覆盖任何?被占据?的格子。
- 我们可以放入任意数目的邮票。
- 邮票可以相互有?重叠?部分。
- 邮票不允许?旋转?。
- 邮票必须完全在矩阵?内?。
如果在满足上述要求的前提下,可以放入邮票,请返回?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;
}
};
文章来源:https://blog.csdn.net/si_mple_/article/details/135005015
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!