A186073.印章落点

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小林准备在一张方格纸上盖印章。方格纸有 nn 行 mm 列,其中一些格子已经有墨迹。

方格纸用一个 0101 矩阵 aa 表示:ai,j=1a_{i,j}=1 表示该格已有墨迹,ai,j=0a_{i,j}=0 表示该格没有墨迹。

印章是一个 hh 行 ww 列的长方形,图案也用一个 0101 矩阵 bb 表示。印章上为 11 的格子会留下墨迹,为 00 的格子不会留下墨迹。保证印章至少有一个格子为 11。

放置印章时,印章的格子必须与方格纸的格子一一对齐,不能旋转或翻转,并且整个 h×wh\times w 的长方形都必须位于方格纸内。

如果印章上所有为 11 的格子,对应的方格纸位置都没有墨迹,那么这个放置位置就是合法的。印章上为 00 的格子可以对应有墨迹或没有墨迹的位置。

请你统计合法放置位置的数量。印章左上角所在格子不同,就视为不同的放置位置。

每个放置位置都独立检查,始终使用最初的方格纸,不会因检查其他位置而改变纸面上的墨迹。

输入格式

第一行输入四个整数 n,m,h,wn,m,h,w,分别表示方格纸的行数、列数,以及印章的行数、列数。

接下来 nn 行,每行输入 mm 个整数,表示矩阵 aa。

接下来 hh 行,每行输入 ww 个整数,表示矩阵 bb。

输出格式

输出一个整数,表示合法放置位置的数量。

输入输出样例

  • 输入#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,1)、(1,2)(1,2)、(2,1)(2,1)、(2,2)(2,2)。例如放在 (1,2)(1,2) 时,印章右上角为 00,因此纸面 (1,3)(1,3) 处已有墨迹不影响合法性。

样例解释 2

印章唯一的落墨格与已有墨迹重叠,没有合法位置。

数据范围

对于所有测试数据,保证:

  • 1≤n,m≤501\le n,m\le50;
  • 1≤h≤min⁡(n,10)1\le h\le\min(n,10),1≤w≤min⁡(m,10)1\le w\le\min(m,10);
  • ai,j,bi,j∈{0,1}a_{i,j},b_{i,j}\in\{0,1\};
  • 矩阵 bb 中至少有一个 11。

输入解题思路,AI测评打分。不知道怎么写?

首页