调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

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

示例 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 <= 105
  • 1 <= m * n <= 2 * 105
  • grid[r][c] 要么是 0 ,要么是 1
  • 1 <= stampHeight, stampWidth <= 105
通过次数
14.2K
提交次数
28K
通过率
50.6%


相关企业

提示 1
We can check if every empty cell is a part of a consecutive row of empty cells that has a width of at least stampWidth as well as a consecutive column of empty cells that has a height of at least stampHeight.

提示 2
We can prove that this condition is sufficient and necessary to fit the stamps while following the given restrictions and requirements.

提示 3
For each row, find every consecutive row of empty cells, and mark all the cells where the consecutive row is at least stampWidth wide. Do the same for the columns with stampHeight. Then, you can check if every cell is marked twice.

相似题目

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 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
Source