[数据结构与算法]【每日一题见微知著】数组前缀查询简化——用邮票贴满网格图-Hard

??寒假新坑——代码之狐的每日做题笔记

2132. 用邮票贴满网格图-Hard

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

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

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

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

class Solution {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m=grid.length;
        int n=grid[0].length;

        int[][] count=new int[m][n];
        for(int x=0;x<m;x++){
            for(int y=0;y<n;y++){
                int mid=grid[x][y];
                if(x!=0)
                    mid+=count[x-1][y];
                if(y!=0)
                    mid+=count[x][y-1];
                if(x!=0&&y!=0)
                    mid-=count[x-1][y-1];
                count[x][y]=mid;
            }
        }
        int[][] k=new int[m][n];
        for(int row=0;row<m;row++){
            for(int col=0;col<n;col++){
                int midr=row+stampHeight-1;
                int midc=col+stampWidth-1;
                boolean index=true;
                if(midr>=m||midc>=n){
                    index=false;
                }
                else{
                    int midCount=count[midr][midc];
                    if(row!=0)
                        midCount-=count[row-1][midc];
                    if(col!=0)
                        midCount-=count[midr][col-1];
                    if(row!=0&&col!=0)
                        midCount+=count[row-1][col-1];
                    if(midCount>=1){
                        index=false;
                    }
                }

                if(index&&grid[row][col]!=1){
                    k[row][col]=1;
                }

                if(row!=0){
                    k[row][col]+=k[row-1][col];
                }
                if(col!=0){
                    k[row][col]+=k[row][col-1];
                }
                if(row!=0&&col!=0){
                    k[row][col]-=k[row-1][col-1];
                }

                if(!index&&grid[row][col]!=1){
                    int midCount=k[row][col];
                    midr=row-stampHeight;
                    midc=col-stampWidth;
                    if(midr>=0)
                        midCount-=k[midr][col];
                    if(midc>=0)
                        midCount-=k[row][midc];
                    if(midc>=0&&midr>=0)
                        midCount+=k[midr][midc];
                    
                    if(midCount<1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

结尾

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems

??关注作者，带你刷题，从简单的算法题了解最常用的算法技能（寒假每日一题）
??关注作者刷题——简单到进阶，让你不知不觉成为无情的刷题机器，有问题请私信