stamping-the-grid

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an <code>m x n</code> binary matrix <code>grid</code> where each cell is either <code>0</code> (empty) or <code>1</code> (occupied).

You are then given stamps of size <code>stampHeight x stampWidth</code>. We want to fit the stamps such that they follow the given restrictions and requirements:

<ol>
	<li>Cover all the empty cells.</li>
	<li>Do not cover any of the occupied cells.</li>
	<li>We can put as many stamps as we want.</li>
	<li>Stamps can overlap with each other.</li>
	<li>Stamps are not allowed to be rotated.</li>
	<li>Stamps must stay completely inside the grid.</li>
</ol>

Return <code>true</code> if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return <code>false</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex1.png" style="width: 180px; height: 237px;" />
<pre>
Input: 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
Output: true
Explanation: We have two overlapping stamps (labeled 1 and 2 in the image) that are able to cover all the empty cells.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex2.png" style="width: 170px; height: 179px;" />
<pre>
Input: grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 
Output: false 
Explanation: There is no way to fit the stamps onto all the empty cells without the stamps going outside the grid.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[r].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 105</code></li>
	<li><code>1 &lt;= m * n &lt;= 2 * 105</code></li>
	<li><code>grid[r][c]</code> is either <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= stampHeight, stampWidth &lt;= 105</code></li>
</ul>

possibleToStamp

Stamping the Grid

Maximal Square

maximal-square

最大正方形

Bomb Enemy

bomb-enemy

轰炸敌人

Matrix Block Sum

matrix-block-sum

矩阵区域和

Greedy

Array

Matrix

Prefix Sum

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

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

<ol>
	<li>覆盖所有 空&nbsp;格子。</li>
	<li>不覆盖任何 被占据&nbsp;的格子。</li>
	<li>我们可以放入任意数目的邮票。</li>
	<li>邮票可以相互有 重叠&nbsp;部分。</li>
	<li>邮票不允许 旋转&nbsp;。</li>
	<li>邮票必须完全在矩阵 内&nbsp;。</li>
</ol>

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

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex1.png" style="width: 180px; height: 237px;">

<pre>输入：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），它们能覆盖所有与空格子。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/ex2.png" style="width: 170px; height: 179px;">

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

&nbsp;

提示：

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[r].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 105</code></li>
	<li><code>1 &lt;= m * n &lt;= 2 * 105</code></li>
	<li><code>grid[r][c]</code> 要么是&nbsp;<code>0</code>&nbsp;，要么是&nbsp;<code>1</code> 。</li>
	<li><code>1 &lt;= stampHeight, stampWidth &lt;= 105</code></li>
</ul>