解題想法#
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\) 總和。
注意
根據題目敘述，我們要得出符合條件的子矩陣數和與矩陣 \(A\) 相差最小的值，因此變數 ans 要設定為無限大，也就是這裡使用的 INT_MAX ，代表 int 的最大值。
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;
}
