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

2023-12-14 22:37:46

给你一个?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;
    }
};

文章来源:https://blog.csdn.net/si_mple_/article/details/135005015
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。