A186073.印章落点
入门
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小林准备在一张方格纸上盖印章。方格纸有 n 行 m 列,其中一些格子已经有墨迹。
方格纸用一个 01 矩阵 a 表示:ai,j=1 表示该格已有墨迹,ai,j=0 表示该格没有墨迹。
印章是一个 h 行 w 列的长方形,图案也用一个 01 矩阵 b 表示。印章上为 1 的格子会留下墨迹,为 0 的格子不会留下墨迹。保证印章至少有一个格子为 1。
放置印章时,印章的格子必须与方格纸的格子一一对齐,不能旋转或翻转,并且整个 h×w 的长方形都必须位于方格纸内。
如果印章上所有为 1 的格子,对应的方格纸位置都没有墨迹,那么这个放置位置就是合法的。印章上为 0 的格子可以对应有墨迹或没有墨迹的位置。
请你统计合法放置位置的数量。印章左上角所在格子不同,就视为不同的放置位置。
每个放置位置都独立检查,始终使用最初的方格纸,不会因检查其他位置而改变纸面上的墨迹。
输入格式
第一行输入四个整数 n,m,h,w,分别表示方格纸的行数、列数,以及印章的行数、列数。
接下来 n 行,每行输入 m 个整数,表示矩阵 a。
接下来 h 行,每行输入 w 个整数,表示矩阵 b。
输出格式
输出一个整数,表示合法放置位置的数量。
输入输出样例
输入#1
3 4 2 2 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1
输出#1
4
输入#2
1 1 1 1 1 1
输出#2
0
说明/提示
样例解释 1
合法位置的左上角分别为 (1,1)、(1,2)、(2,1)、(2,2)。例如放在 (1,2) 时,印章右上角为 0,因此纸面 (1,3) 处已有墨迹不影响合法性。
样例解释 2
印章唯一的落墨格与已有墨迹重叠,没有合法位置。
数据范围
对于所有测试数据,保证:
- 1≤n,m≤50;
- 1≤h≤min(n,10),1≤w≤min(m,10);
- ai,j,bi,j∈{0,1};
- 矩阵 b 中至少有一个 1。
输入解题思路,AI测评打分。不知道怎么写?