矩陣總和

解題想法

1. 設立二維陣列

題目敘述中提到， $s, t, n, m$ 分別為矩陣 $A$ 和矩陣 $B$ 的長寬，因此可以依照題意，創建以下變數：

int s, t, n, m, r, total = 0, ans = INT_MAX, asum = 0;
int a[15][105], b[15][105];

以上除了題目提到的正整數外，還有 total, ans, asum 這三個變數，分別計算子矩陣總和、相差最小值和矩陣 $A$ 總和。

2. 輸入矩陣

在輸入矩陣時，我們可以在同時計算矩陣 $A$ 的總和，如下：

for (int i = 1; i <= s; i++) {
    for (int j = 1; j <= t; j++) {
        cin >> a[i][j];
        asum += a[i][j];
    }
} 
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> b[i][j];
    }
}

3. 檢查所有子矩陣 ( 枚舉 )

在題目敘述中，需要我們檢查所有可能的子矩陣，也就是大小跟矩陣 $A$ 一樣，但不超過矩陣 $B$ 的範圍。

我們在前面章節中提到，如果我們呼叫超出範圍的陣列元素時，會得到記憶體區位段錯誤，所以我們可以用以下程式，確保我們不會取到不適合的索引值，如下：

for (int i = 1; i <= n - s + 1; i++){
    for (int j = 1; j <= m - t + 1; j++){
        //...
    }
}

以上為一個雙層迴圈，其中只會跑 $[1, (n - s + 1)], [1, (m - t + 1)]$ 的範圍，確保我們不會輸入不正確的索引值。

之後就是枚舉所有子矩陣，並且算出兩矩陣的元素不相同數，從而判斷是否符合題目要求，即元素不相同數不超過 $r$：

int tmp = 0;
int diff = 0;
for (int x = 1; x <= s; x++) {
    for (int y = 1; y <= t; y++) {
        diff += (b[i + x - 1][j + y - 1] != a[x][y] ? 1 : 0);
        tmp += b[i + x - 1][j + y - 1];
    }
}

如果符合要求，我們就會計算兩矩陣相差值，並且比較是否為新的最小值：

if (diff <= r) {
    total++;
    ans = min(abs(tmp - asum), ans);
}   

4. 輸出答案

本題有一個小細節，就是當沒有子矩陣符合條件時，第二行要輸出 $-1$，因此在程式的最後可以增加其三元判斷式：

cout << total << '\n' << (ans == INT_MAX ? -1 : ans) << '\n';

以上式子會判斷變數 ans 是否被改值，如果沒有，就輸出 $-1$ ，否則輸出 ans 。

範例程式

#include <bits/stdc++.h>
using namespace std;

int s, t, n, m, r, total = 0, ans = INT_MAX, asum = 0;
int a[15][105], b[15][105];

int main() {
    cin >> s >> t >> n >> m >> r; 
    for (int i = 1; i <= s; i++) {
        for (int j = 1; j <= t; j++) {
            cin >> a[i][j];
            asum += a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
        }
    }
    for (int i = 1; i <= n - s + 1; i++) {
        for (int j = 1; j <= m - t + 1; j++) {
            int tmp = 0;
            int diff = 0;
            for (int x = 1; x <= s; x++) {
                for (int y = 1; y <= t; y++) {
                    diff += (b[i + x - 1][j + y - 1] != a[x][y] ? 1 : 0);
                    tmp += b[i + x - 1][j + y - 1];
                }
            }
            if (diff <= r) {
                total++;
                ans = min(abs(tmp - asum), ans);
            }
        }
    }
    cout << total << '\n' << (ans == INT_MAX ? -1 : ans) << '\n';
    return 0;
}