AT_abc278_e [ABC278E] Grid Filling

题目描述

有一个纵向 $H$ 行、横向 $W$ 列的网格。自上而下第 $i$ 行，自左而右第 $j$ 列的格子记作 $(i,j)$。在每个 $(i,j)\ (1\leq i\leq H,1\leq j\leq W)$ 上写有一个 $1$ 到 $N$ 之间的整数 $A_{i,j}$。

给定整数 $h,w$。对于所有满足 $0\leq k\leq H-h,0\leq l\leq W-w$ 的 $(k,l)$ 组合，请解决以下问题：

• 当你将所有满足 $k<i\leq k+h,\, l<j\leq l+w$ 的 $(i,j)$ 格子涂黑时，求未被涂黑的格子上写着的数有多少种。

注意，解题时不需要实际去涂黑格子（每个问题都是独立的）。

输入格式

输入以以下格式从标准输入给出。

$H$ $W$ $N$ $h$ $w$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$

输出格式

对于每个 $(k,l)$，输出答案 $\operatorname{ans}_{k,l}$，格式如下：

$\operatorname{ans}_{0,0}$ $\operatorname{ans}_{0,1}$ $\dots$ $\operatorname{ans}_{0,W-w}$
$\operatorname{ans}_{1,0}$ $\operatorname{ans}_{1,1}$ $\dots$ $\operatorname{ans}_{1,W-w}$
$\vdots$
$\operatorname{ans}_{H-h,0}$ $\operatorname{ans}_{H-h,1}$ $\dots$ $\operatorname{ans}_{H-h,W-w}$

输入输出样例 #1

输入 #1

3 4 5 2 2
2 2 1 1
3 2 5 3
3 4 4 3

输出 #1

4 4 3
5 3 4

输入输出样例 #2

输入 #2

5 6 9 3 4
7 1 5 3 9 5
4 5 4 5 1 2
6 1 6 2 9 7
4 7 1 5 8 8
3 4 3 3 5 3

输出 #2

8 8 7
8 9 7
8 9 8

输入输出样例 #3

输入 #3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

输出 #3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

说明/提示

限制条件

• $1\leq H,W,N\leq 300$
• $1\leq h\leq H$
• $1\leq w\leq W$
• $(h,w)\neq(H,W)$
• $1\leq A_{i,j}\leq N\ (1\leq i\leq H,1\leq j\leq W)$
• 所有输入的值均为整数

样例说明 1

给定的棋盘如下图所示。

例如，当 $(k,l)=(0,0)$ 时，未被涂黑的格子上写着的数有 $1,3,4,5$ 共 $4$ 种，因此答案为 $4$。

由 ChatGPT 4.1 翻译