c044. 202001_2 矩陣總和

Content

矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (row)，直排稱為行 (column)，一個$n \times m$的矩陣有 $n$ 列 $m$ 行，其中以 $X_{ij}$ 來表示矩陣 $X$ 中的第 $i$ 列第 $j$ 行的元素。在同樣大小的矩陣中，我們定義兩個矩陣的距離為兩矩陣中對應位置相同但值不相同的元素數量。

有一個 $s \times t$ 的小矩陣 $A$，和一個 $n \times m$ 的大矩陣 $B$，請計算 $B$ 矩陣的子矩陣中，與 $A$ 矩陣距離不超過 $r$ 的子矩陣個數，並從這些距離 $A$ 不超過 $r$ 的子矩陣中，找到總和與 $A$ 差異最小的值。

以範例二為例，$B$ 矩陣中有3個子矩陣與 $A$ 距離不超過 $2$，其中 $A$ 的元素總和為 $1+2+1+2+4+2+2+4+5=23$，$B_1$ 的元素總和為$20$，$B_2$ 的元素總和為 $24$ ，$B_3$ 的元素總和為 $28$。與 $A$ 元素總和最小值的為 $|23-24| = 1$。

Input

第一行有五個正整數$s$，$t$，$n$，$m$ 與 $r$。

接下來 $s$ 行(line)每行包含 $t$ 個數，第 $i$ 行第 $j$ 個數代表小矩陣 $A_{ij}$ 的值。

接下來 $n$ 行(line)每行包含 $m$ 個數，第 $i$ 行第 $j$ 個數代表大矩陣 $B_{ij}$ 的值。

同一行間數字以空格隔開。

測資範圍如下：

$1 \leq s \leq n \leq 10$
$1 \leq t \leq m \leq 100$
$1 \leq r \leq 100$
$0 \leq A_{ij},B_{ij}≤9$

本題包含三個子題組，每個子題組配分如下：

第 1 子題組共 50 分： $s = n = 1$
第 2 子題組共 50 分：無額外限制。

Output

輸出有兩行。第一行輸出符合條件的子矩陣個數。

第二行輸出所有符合條件的子矩陣中，數字總和與$A$相差最小的值，若找不到符合條件的子矩陣，則最小值輸出$-1$。

Sample Input #1

1 3 1 10 1
7 4 7
6 7 7 7 4 5 0 4 4 7

Sample Output #1

3
2

Sample Input #2

Sample Output #2

3
1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

Tags:

出處:

2020年1月 APCS 演算法海牛 [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」