矩陣總和 (APCS 2020-01 中級)

一個 \(n\times m\) 的矩陣有 \(n\) 列（row）與 \(m\) 行（column）。矩陣 \(X\) 中第 \(i\) 列、第 \(j\) 行的元素記為 \(X_{i,j}\)。

對兩個大小相同的矩陣，我們把對應位置數值不同的元素個數稱為它們的矩陣距離。例如：

在右上角與右下角的值不同，所以兩個矩陣的距離是 \(2\)。

現在給定一個 \(s\times t\) 的小矩陣 \(A\)，以及一個 \(n\times m\) 的大矩陣 \(B\)。在 \(B\) 中選取連續 \(s\) 列與連續 \(t\) 行，便得到一個與 \(A\) 大小相同的子矩陣。

若子矩陣左上角位於 \(B\) 的第 \(x\) 列、第 \(y\) 行，則它包含

合法的左上角共有

請檢查每一個這樣的子矩陣：

1. 若它與 \(A\) 的矩陣距離不超過 \(r\)，便稱為符合條件。
2. 第一行輸出符合條件的子矩陣個數。
3. 對每個符合條件的子矩陣，再比較「子矩陣所有元素的總和」與「\(A\) 所有元素的總和」，找出兩者絕對差的最小值。

矩陣距離只用來判斷是否符合條件；第二行比較的是元素總和，兩者不要混淆。同一個位置若屬於多個重疊的子矩陣，這些子矩陣仍要分別計算。

輸入格式

第一行包含五個正整數 \(s,t,n,m,r\)。

接下來 \(s\) 行，每行包含 \(t\) 個整數，表示矩陣 \(A\)。

再接下來 \(n\) 行，每行包含 \(m\) 個整數，表示矩陣 \(B\)。

限制

• \(1\le s\le n\le10\)
• \(1\le t\le m\le100\)
• \(1\le r\le100\)
• \(0\le A_{i,j},B_{i,j}\le9\)
• 所有輸入都是整數。

輸出格式

第一行輸出與 \(A\) 的矩陣距離不超過 \(r\) 的子矩陣個數。

若至少有一個符合條件的子矩陣，第二行輸出它們與 \(A\) 的元素總和絕對差的最小值；若完全沒有符合條件的子矩陣，第二行輸出 \(-1\)。

評分說明

兩筆範例會由評測系統執行，但不計分。另有恰好 \(20\) 個計分子題組，每組 \(5\) 分：

• 第 \(1\)～\(10\) 組（共 \(50\) 分）：\(s=n=1\)。
• 第 \(11\)～\(20\) 組（共 \(50\) 分）：沒有額外限制。

範例輸入 1

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

範例輸出 1

3
2

範例解釋 1

矩陣 \(B\) 中共有 \(8\) 個長度為 \(3\) 的連續子矩陣，其中有 \(3\) 個與 \(A=[7,4,7]\) 的矩陣距離不超過 \(1\)。比較這三個子矩陣的元素總和後，最小絕對差為 \(2\)。

範例輸入 2

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

範例輸出 2

3
1

範例解釋 2

符合條件的三個子矩陣左上角分別是 \((1,1)\)、\((1,3)\)、\((3,2)\)，它們的矩陣距離依序為 \(1,2,2\)。

\(A\) 的元素總和為 \(23\)，三個子矩陣的元素總和依序為 \(20,24,28\)，所以最小絕對差為

題目來源

APCS 2020 年 1 月實作題第 2 題；規則參考 ZeroJudge h027「矩陣總和」 與王一哲的題解，題目敘述由 AACPOJ 重新整理。