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

簡潔題意

兩個一樣大的矩陣，「矩陣距離」＝對應位置數值不同的元素個數。給 \(s \times t\) 的小矩陣 \(A\) 和 \(n \times m\) 的大矩陣 \(B\)（\(1 \le s \le n \le 10\)、\(1 \le t \le m \le 100\)、元素都是 \(0 \sim 9\)），\(B\) 裡每一個 \(s \times t\) 的子矩陣若與 \(A\) 的距離不超過 \(r\)（\(1 \le r \le 100\)）就算符合條件。第一行輸出符合條件的子矩陣個數；第二行輸出這些子矩陣裡「元素總和」與「\(A\) 的元素總和」絕對差的最小值，一個都不符合就輸出 \(-1\)。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(50\) 分）：\(s = n = 1\)。
  • 子題組 2（\(50\) 分）：無額外限制。

先拿下子題組 1（50 分）：只有一列，就是滑動窗口

\(s = n = 1\) 時 \(A\) 是一排 \(t\) 個數、\(B\) 是一排 \(m\) 個數，兩個一維陣列裝得下（上冊 6.1）。「\(B\) 的子矩陣」就是 \(B\) 裡連續 \(t\) 個數——左端 left 從 \(0\) 開始、每次右移一格，left + t <= m 才放得下。對每個位置算兩件事：

  1. 距離：A[j] 對上 B[left + j]，逐格比，不一樣就加一。
  2. 總和：把 B[left + j] 加起來。

距離不超過 r 才算符合：計數加一，並用總和差的絕對值打擂台更新最小值（上冊 3.9）。絕對值直接 abs()（上冊 7.6）。擂主的初值要比所有可能的差都大——用 <climits> 的 INT_MAX（上冊 2.3），而不是 \(-1\)：\(-1\) 跟任何差比都會輸，最小值永遠更新不了。最後先看計數是不是 \(0\)：是就印 \(-1\)，否則才印最小差——不然沒有符合的時候印出來的是 INT_MAX。

#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;

const int MAX_M = 100;

int main() {
    int s, t, n, m, r;
    cin >> s >> t >> n >> m >> r;     // 子題組 1 保證 s = n = 1：A、B 都只有一列
    int A[MAX_M], B[MAX_M];
    int sumA = 0;
    for (int j = 0; j < t; j++) {
        cin >> A[j];
        sumA += A[j];
    }
    for (int j = 0; j < m; j++) cin >> B[j];

    int eligibleCount = 0;
    int minimumSumDifference = INT_MAX;
    for (int left = 0; left + t <= m; left++) {   // 子矩陣的左端：要放得下 t 個
        int distance = 0;
        int sumB = 0;
        for (int j = 0; j < t; j++) {             // A 的第 j 個對應 B 的第 left + j 個
            sumB += B[left + j];
            if (B[left + j] != A[j]) distance++;
        }
        if (distance <= r) {
            eligibleCount++;
            if (abs(sumA - sumB) < minimumSumDifference) minimumSumDifference = abs(sumA - sumB);
        }
    }

    cout << eligibleCount << '\n';
    if (eligibleCount == 0) {
        cout << -1 << '\n';
    } else {
        cout << minimumSumDifference << '\n';
    }
    return 0;
}

這份程式交上去，範例 2 和子題組 2 會 WA——這是正常的，逐筆給分之下子題組 1 的 \(50\) 分穩穩到手。

從 50 分到 100 分：枚舉左上角，每一格都加同一個位移

二維版只多一件事：子矩陣不再只有「左端」，而是有一個左上角 \((top, left)\)；\(A\) 的 \((i, j)\) 對到 \(B\) 的 \((top + i, left + j)\)——每一格都加同一個位移，就是 13.8 的平移。要試遍所有子矩陣＝枚舉左上角：top 要放得下 \(s\) 列（top + s <= n）、left 要放得下 \(t\) 行（left + t <= m）。這兩個上界寫對，子矩陣永遠不會伸出 \(B\) 外面，連 inside 都不用。

外面兩層迴圈枚舉左上角、裡面兩層迴圈逐格比對（上冊 4.6 的巢狀迴圈），每個子矩陣算出 distance 和 sumB 之後的判斷跟一維版一模一樣。地圖用巢狀 vector 讀（13.1），\(A\) 的總和在讀入時順便加好。

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

int main() {
    int s, t, n, m, r;
    cin >> s >> t >> n >> m >> r;
    vector<vector<int>> A(s, vector<int>(t));
    vector<vector<int>> B(n, vector<int>(m));
    int sumA = 0;
    for (int i = 0; i < s; i++) {
        for (int j = 0; j < t; j++) {
            cin >> A[i][j];
            sumA += A[i][j];
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> B[i][j];

    int eligibleCount = 0;
    int minimumSumDifference = INT_MAX;
    for (int top = 0; top + s <= n; top++) {           // 左上角的橫排：要放得下 s 列
        for (int left = 0; left + t <= m; left++) {    // 左上角的直排：要放得下 t 行
            int distance = 0;
            int sumB = 0;
            for (int i = 0; i < s; i++) {              // A 的 (i, j) 對應 B 的 (top+i, left+j)
                for (int j = 0; j < t; j++) {
                    const int value = B[top + i][left + j];
                    sumB += value;
                    if (value != A[i][j]) distance++;
                }
            }
            if (distance <= r) {
                eligibleCount++;
                minimumSumDifference = min(minimumSumDifference, abs(sumA - sumB));
            }
        }
    }

    cout << eligibleCount << '\n';
    if (eligibleCount == 0)
        cout << -1 << '\n';
    else
        cout << minimumSumDifference << '\n';
    return 0;
}

min 和 abs 取代了一維版的兩行 if（上冊 7.6），意思完全一樣。運算量：左上角最多 \(10 \times 100\) 個、每個子矩陣最多 \(10 \times 100\) 格，四層迴圈總共 \(10^6\) 次，一秒內輕鬆跑完。總和最大 \(1000 \times 9 = 9000\)，int 綽綽有餘。

測過再交：兩個範例都「有符合的子矩陣」

兩個範例第二行都是正常的數字，從來沒有印過 \(-1\)；範例 2 的 \(A\) 和 \(B\) 又都是正方形。「沒有符合的時候印什麼」和「長寬不一樣時迴圈上界對不對」都得自己補：

輸入 正確輸出 這一筆在測什麼
1 2 1 3 1 ／ 5 5 ／ 0 0 0 0 ／ -1 沒有任何子矩陣符合：沒特別處理的程式印 2147483647（擂主初值）或 0——兩個範例都抓不到
1 2 3 2 1 ／ 1 1 ／ 0 0 ／ 0 0 ／ 1 1 1 ／ 0 \(A\)、\(B\) 都不是正方形（範例 2 是 \(3 \times 3\) 套 \(5 \times 5\)）：唯一符合的子矩陣在最後一列、總和差是 \(0\)。迴圈上界把 \(s\) 和 \(t\) 搞混的程式印 0／-1
2 2 2 2 4 ／ 1 2 ／ 3 4 ／ 9 9 ／ 9 9 1 ／ 26 \(A\) 跟 \(B\) 一樣大＝只有一個子矩陣；四格全不同、距離剛好等於 \(r\)，等號也算符合
1 2 1 3 6 ／ 1 1 ／ 5 5 5 2 ／ 8 \(r\) 比格數還大＝每個子矩陣都符合；子題組 1 版就能驗

四筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 沒有符合的子矩陣時忘了印 \(-1\)：兩個範例全過；自測表第 1 列印 2147483647 或 0。
  • 迴圈上界寫成 top + s < n、left + t < m：最後一列、最後一行的子矩陣沒算到——範例 1 只有一列，迴圈一次都沒跑，印 0／-1；範例 2 印 1／3。
  • 第二行拿矩陣距離去算最小值：題目第二行比的是元素總和——範例 1 印 3／1（該印 3／2）。
  • 最小差在所有子矩陣上算、不是只看符合條件的：範例 1 印 3／0。
  • 距離的判斷寫成 < r：不超過 \(r\) 是含等號的——範例 1 印 0／-1。
  • 總和差忘了取絕對值：範例 1 印 3／-3。