242037 - 张贴邮票

题目描述

空间站下层区的深空当铺里,乔·王尔德盯着一面旧展示墙发愁。墙上空出来的格子要重新贴满他收藏的旧邮票,可这活儿没那么简单。

这面墙可以看成一个 m × n 的二进制矩阵 grid:0 表示这个格子是空的,1 表示这个格子已经被货物占据。王尔德手里只有一种邮票,尺寸为 stampHeight × stampWidth。

贴邮票要同时满足以下限制与要求:

  1. 邮票不能旋转,必须完全落在墙面范围内,不能伸出边界;
  2. 可以贴任意数目的邮票,邮票之间允许互相重叠;
  3. 每张邮票覆盖的格子必须全是空格,不能覆盖任何被占据的格子;
  4. 墙面上的所有空格子都必须至少被一张邮票覆盖。

王尔德敲了敲柜台:「能贴满吗?」如果存在满足上述全部要求的贴法,输出 YES;否则输出 NO。

输入

第一行两个整数 m、n,表示矩阵的行数与列数。

第二行两个整数 stampHeight、stampWidth,表示邮票的高与宽。

接下来 m 行,每行 n 个整数(0 或 1),相邻整数用一个空格隔开,描述矩阵 grid。

输出

一行一个字符串:如果能够贴满所有空格,输出 YES,否则输出 NO。

样例

输入

5 4
4 3
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0

输出

YES
说明

对所有测试数据,1 ≤ m, n ≤ 10^5,1 ≤ m × n ≤ 10^6,1 ≤ stampHeight, stampWidth ≤ 10^5,矩阵 grid 中只会出现 0 和 1。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 5 枚
难度 提高


上一题 下一题