13.8 平移與子矩陣
平移就是每一格都加上同一個位移：把小圖 A 疊到大圖 B 上、左上角對齊 (top, left)，那麼 A 的 (i, j) 對到的是 B 的 (top + i,\ left + j)。要試遍所有位置，就是枚舉左上角——這也是「在大圖裡找子矩陣」的標準寫法。
¶例題：矩陣總和（APCS 2020 年 1 月中級）
題目：兩個同大小矩陣的「矩陣距離」＝對應位置數值不同的元素個數。給 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。
#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;
}
迴圈上界寫 top + s <= n、left + t <= m，子矩陣就永遠不會伸出 B 外，連 inside 都不用；四層迴圈的總量是 10 \times 100 \times 10 \times 100 = 10^6，一秒內輕鬆跑完。
¶延伸：形狀打表與碰撞
平移的另一個長相是「把一個形狀放進格子裡、往某個方向推」。形狀不規則怎麼辦？把形狀打成表——列出它每一個方格相對於某個基準點的位移，之後「放在某處會不會出界或撞到東西」就是把表跑一遍逐格檢查。
運貨站（APCS 2022 年 10 月中級）：R \times C 的倉庫（R \le 30、C \le 50）依序收到 n 件貨物（n \le 200），形狀是 A～E 五種之一、方向固定，最上方位於第 y_i 列。貨物先試「剛好完全進入倉庫」的最右位置——放不下就丟棄；放得下就一格一格往左推，直到再往左會出界或碰到別的貨物為止。輸出最後倉庫的空格數與被丟棄的貨物數。
#include <bits/stdc++.h>
using namespace std;
// 五種形狀打成表：每個方格相對於「最上列、最右行」的位移 (dr, dc)
vector<pair<int, int>> shape(char type) {
if (type == 'A') return {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
if (type == 'B') return {{0, -2}, {0, -1}, {0, 0}};
if (type == 'C') return {{0, -1}, {0, 0}, {1, -1}, {1, 0}};
if (type == 'D') return {{0, 0}, {1, -2}, {1, -1}, {1, 0}};
return {{0, 0}, {1, -1}, {1, 0}, {2, -1}, {2, 0}}; // E
}
int R, C;
vector<vector<bool>> occupied;
// 把形狀的最右行放在第 right 行、最上列放在第 top 列，放得下嗎？
bool canPlace(int top, int right, const vector<pair<int, int>>& cells) {
for (auto [dr, dc] : cells) {
int r = top + dr, c = right + dc;
if (r < 0 || r >= R || c < 0 || c >= C) return false; // 出界
if (occupied[r][c]) return false; // 撞到別的貨物
}
return true;
}
int main() {
int n;
cin >> R >> C >> n;
occupied.assign(R, vector<bool>(C, false));
int used = 0, discarded = 0;
while (n--) {
char type;
int top;
cin >> type >> top;
vector<pair<int, int>> cells = shape(type);
int right = C - 1; // 先試「剛好完全進入倉庫」的最右位置
if (!canPlace(top, right, cells)) { discarded++; continue; }
while (canPlace(top, right - 1, cells)) right--; // 還能往左就繼續推
for (auto [dr, dc] : cells) occupied[top + dr][right + dc] = true;
used += cells.size();
}
cout << R * C - used << ' ' << discarded << '\n';
return 0;
}
shape() 回傳的就是那張表：把題目附圖裡每個方格的位置照抄成 (dr, dc)。之後平移形狀＝改變基準點 (top, right)，檢查碰撞＝把表跑一遍——和 13.3 的方向表是同一種思路：會重複用到的一組座標，就打成表。