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\lt i\leq k+h$ 且 $l\lt j\leq l+w$ 的格子涂黑，那么在未被涂黑的格子上写着多少个不同的整数？

注意，你并不真的去涂黑这些格子（也就是说，各个问题之间相互独立）。

输入格式

输入由标准输入按照以下格式给出： $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}$

输出格式

以如下格式输出答案，其中 $\operatorname{ans}_{k,l}$ 表示对 $(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}$

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

4 4 3
5 3 4

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

8 8 7
8 9 7
8 9 8

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

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)$ 输入中的所有数值均为整数。给定的网格如下所示： 例如，当 $(k,l)=(0,0)$ 时，未被涂黑的格子上写着四个不同的整数 $1,3,4$ 和 $5$，所以答案为 $4$.

标签: AtCoder|abc278E

来源

AtCoder|abc278E