2132. 用邮票贴满网格图

题目描述

给你一个 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），它们能覆盖所有与空格子。

示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
输出：false 
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：

m == grid.length
n == grid[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 2 * 10⁵
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 10⁵

解法

方法一：二维前缀和 + 二维差分

s[i + 1][j + 1] 表示第 i 行第 j 列左上部分所有元素之和，其中 i, j 下标从 0 开始。

则 s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + nums[i][j]。

以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵和 sub = s[x2 + 1][y2 + 1] - s[x2 + 1][y1] - s[x1][y2 + 1] + s[x1][y1]。

Python3

class Solution:
    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:
        m, n = len(grid), len(grid[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + v

        d = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v == 0:
                    x, y = i + stampHeight, j + stampWidth
                    if x <= m and y <= n and s[x][y] - s[x][j] - s[i][y] + s[i][j] == 0:
                        d[i][j] += 1
                        d[i][y] -= 1
                        d[x][j] -= 1
                        d[x][y] += 1

        cnt = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j]
                if v == 0 and cnt[i + 1][j + 1] == 0:
                    return False
        return True

Java

class Solution {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int m = grid.length, n = grid[0].length;
        int[][] s = new int[m + 1][n + 1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
            }
        }
        int[][] d = new int[m + 1][n + 1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    int x = i + stampHeight, y = j + stampWidth;
                    if (x <= m && y <= n && s[x][y] - s[x][j] - s[i][y] + s[i][j] == 0) {
                        d[i][j]++;
                        d[i][y]--;
                        d[x][j]--;
                        d[x][y]++;
                    }
                }
            }
        }
        int[][] cnt = new int[m + 1][n + 1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j];
                if (grid[i][j] == 0 && cnt[i + 1][j + 1] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> s(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
            }
        }
        vector<vector<int>> d(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j]) continue;
                int x = i + stampHeight, y = j + stampWidth;
                if (x <= m && y <= n && s[x][y] - s[i][y] - s[x][j] + s[i][j] == 0)
                {
                    d[i][j]++;
                    d[x][j]--;
                    d[i][y]--;
                    d[x][y]++;
                }
            }
        }
        vector<vector<int>> cnt(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j];
                if (grid[i][j] == 0 && cnt[i + 1][j + 1] == 0) return false;
            }
        }
        return true;
    }
};

Go

func possibleToStamp(grid [][]int, stampHeight int, stampWidth int) bool {
	m, n := len(grid), len(grid[0])
	s := make([][]int, m+1)
	d := make([][]int, m+1)
	cnt := make([][]int, m+1)
	for i := range s {
		s[i] = make([]int, n+1)
		d[i] = make([]int, n+1)
		cnt[i] = make([]int, n+1)
	}
	for i, row := range grid {
		for j, v := range row {
			s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + v
		}
	}
	for i, row := range grid {
		for j, v := range row {
			if v == 0 {
				x, y := i+stampHeight, j+stampWidth
				if x <= m && y <= n && s[x][y]-s[i][y]-s[x][j]+s[i][j] == 0 {
					d[i][j]++
					d[i][y]--
					d[x][j]--
					d[x][y]++
				}
			}
		}
	}
	for i, row := range grid {
		for j, v := range row {
			cnt[i+1][j+1] = cnt[i+1][j] + cnt[i][j+1] - cnt[i][j] + d[i][j]
			if v == 0 && cnt[i+1][j+1] == 0 {
				return false
			}
		}
	}
	return true
}

JavaScript

/**
 * @param {number[][]} grid
 * @param {number} stampHeight
 * @param {number} stampWidth
 * @return {boolean}
 */
var possibleToStamp = function (grid, stampHeight, stampWidth) {
    const m = grid.length;
    const n = grid[0].length;
    let s = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    let d = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    let cnt = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
        }
    }
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] == 0) {
                let [x, y] = [i + stampHeight, j + stampWidth];
                if (
                    x <= m &&
                    y <= n &&
                    s[x][y] - s[i][y] - s[x][j] + s[i][j] == 0
                ) {
                    d[i][j]++;
                    d[i][y]--;
                    d[x][j]--;
                    d[x][y]++;
                }
            }
        }
    }
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            cnt[i + 1][j + 1] =
                cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j];
            if (grid[i][j] == 0 && cnt[i + 1][j + 1] == 0) {
                return false;
            }
        }
    }
    return true;
};

挥剑_转身_天涯 / leetcode

2132. 用邮票贴满网格图

题目描述

解法

Python3

Java

C++

Go

JavaScript

TypeScript

...

简介

发行版

贡献者

近期动态

挥剑_转身_天涯 / leetcode .gitee-modal { width: 500px !important; }

2132. 用邮票贴满网格图

题目描述

解法

Python3

Java

C++

Go

JavaScript

TypeScript

...

简介

发行版

贡献者

近期动态

搜索帮助

挥剑_转身_天涯 / leetcode