给你一个 m x n 的二进制矩阵 grid 。

  • grid[i][j] = 0 表示该格子是空的
  • grid[i][j] = 1 表示该格子被占用
    再给你一个邮票尺寸：
    stampHeight x stampWidth
    你可以放置任意数量的邮票，满足：

放置规则

  1. 邮票只能放在 全部是 0 的区域（不能覆盖 1）
  2. 邮票不能旋转
  3. 邮票必须完全在矩阵内部
  4. 邮票之间可以重叠
  5. 最终必须覆盖 所有 0 格子

目标

如果可以通过放置若干邮票，使所有 0 都被覆盖，则返回 true，否则返回 false。

🔍 举个例子

输入：
grid = [ [1,0,0], [1,0,0], [1,0,0] ] stampHeight = 2 stampWidth = 2
输出：
true
因为可以贴两张 2x2 的邮票覆盖所有 0

我们可以先对整个网格图进行二维前缀和,另外开辟一个数组和网格图等大初始化为0去记录每个格子是否被覆盖。我们统计每个stampHeight x stampWidth区域的和是否为0,如果为0,则将新开辟数组对应区域加1。最后我们统计网格图值为0的格子覆盖次数是否大于等于1。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int m,n,h,w;
    cin>>m>>n>>h>>w;
    vector<vector<int>>grid(m+1,vector<int>(n+1,0));
    vector<vector<int>>add(m+1,vector<int>(n+1,0));
    vector<vector<int>>op(m+2,vector<int>(n+2,0));
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    {
        cin>>grid[i][j];
        add[i][j]=grid[i][j];
    }
    for(int i=1;i<=m;i++)
    for(int j=2;j<=n;j++)
    add[i][j]+=add[i][j-1];
    for(int i=1;i<=n;i++)
    for(int j=2;j<=m;j++)
    add[j][i]+=add[j-1][i];
    for(int i=h;i<=m;i++)
    for(int j=w;j<=n;j++)
    {
        if(add[i][j]-add[i][j-w]-add[i-h][j]+add[i-h][j-w]==0)
        {
            op[i+1][j+1]+=1;
            op[i-h+1][j-w+1]+=1;
            op[i+1][j-w+1]-=1;
            op[i-h+1][j+1]-=1;
        }
    }
    for(int i=0;i<=m+1;i++)
    for(int j=1;j<=n+1;j++)
    op[i][j]+=op[i][j-1];
    for(int i=0;i<=n+1;i++)
    for(int j=1;j<=m+1;j++)
    op[j][i]+=op[j-1][i];
    int flag=1;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
    if(grid[i][j]==0&&op[i][j]==0)
    flag=0;
    if(flag==1)
    cout<<"true";
    else
    cout<<"false";
}