# APCS實作題2020年1月第2題：矩陣總和

> 日期：2023年9月22日
> 作者：王一哲
> 題目來源：109年1月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=h027)

<br />

## 題目

### 問題描述

矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (row)，直排稱為行 (column)，一個的矩陣有 $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$。
<br />

### 輸入說明

第一行有五個正整數 $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} \leq 9$

本題包含三個子題組，每個子題組配分如下：
- 第1子題組共50分：$s=n=1$
- 第2子題組共50分：無額外限制。

<br />

### 輸出說明

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

<br />

### 範例一：輸入

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

### 範例一：正確輸出

3
2

<br />

### 範例二：輸入

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

### 範例二：正確輸出

3
1

<br />

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 54 ms，使用記憶體最多約為 3.4 MB，通過測試。

s, t, n, m, r = map(int, input().split())  # 讀取s, t, n, m, r
A, B = [], []  # 儲存矩陣 A, B 用的二維串列
sumA, num, ans = 0, 0, 100000  # 矩陣A的總和，符合條件的子矩陣個數，矩陣A與子矩陣最小的距離先預設為100000
for _ in range(s):  # 讀取矩陣A
    tmp = list(map(int, input().split()))  # 整行資料用空格分格並暫存成串列 tmp
    sumA += sum(tmp)  # 計算 tmp 的總和再加到 sumA
    A.append(tmp)  # 將 tmp 加到 A
for _ in range(n): B.append(list(map(int, input().split())))  # 讀取矩陣A

for i in range(n-s+1):  # 於B找子矩陣時列的平移量
    for j in range(m-t+1):  # 於B找子矩陣時行的平移量
        dis, sumB = 0, 0  # 矩陣距離，子矩陣總和
        for x in range(s):  # 依序讀取A及子矩陣的元素
            for y in range(t):
                sumB += B[x+i][y+j]  # 計算子矩陣總和
                if A[x][y] != B[x+i][y+j]: dis += 1  # 如果對應位置的元素不相等，dis 加1
        if dis <= r:  # 如果距離小於等於r
            num += 1  # 符合條件的子矩陣數量加1
            ans = min(ans, abs(sumA - sumB))  # 更新距離最小值

print(num)  # 印出符合條件的子矩陣數量
print(ans if ans != 100000 else "-1")  # 印出符合條件的子矩陣最小距離，如果沒有符合條件的子矩陣則印出 -1

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 4 ms，使用記憶體最多約為 340 kB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // 依序為矩陣A的列數、行數，矩陣B的列數、行數，距離條件，矩陣A的總和，符合條件的子矩陣個數，矩陣A與子矩陣最小的距離先預設為100000
    int s, t, n, m, r, sumA = 0, num = 0, ans = 100000;
    cin >> s >> t >> n >> m >> r;  // 讀取s, t, n, m, r
    int A[s][t], B[n][m];  // 儲存矩陣 A, B 用的二維陣列
    for(int i=0; i<s; i++) {  // 讀取矩陣A
        for(int j=0; j<t; j++) {
            int tmp; cin >> tmp;
            sumA += tmp;
            A[i][j] = tmp;
        }
    }
    for(int i=0; i<n; i++) {  // 讀取矩陣B
        for(int j=0; j<m; j++) {
            cin >> B[i][j];
        }
    }
    
    for(int i=0; i<=n-s; i++) {  // 於B找子矩陣時列的平移量
        for(int j=0; j<= m-t; j++) {  // 於B找子矩陣時行的平移量
            int dis = 0, sumB = 0;  // 矩陣距離，子矩陣總和
            for(int x=0; x<s; x++) {  // 依序讀取A及子矩陣的元素
                for(int y=0; y<t; y++) {
                    sumB += B[x+i][y+j];  // 計算子矩陣總和
                    if (A[x][y] != B[x+i][y+j]) dis++;  // 如果對應位置的元素不相等，dis 加1
                }
            }
            if (dis <= r) {  // 如果距離小於等於r
                num++;  // 符合條件的子矩陣數量加1
                ans = min(ans, abs(sumA - sumB));  // 更新距離最小值
            }
        }
    }

    cout << num << endl;  // 印出符合條件的子矩陣數量
    (ans != 100000) ? cout << ans << endl : cout << "-1" << endl;  // 印出符合條件的子矩陣最小距離，如果沒有符合條件的子矩陣則印出 -1
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`