航空拍照圖 題解|APCS 2025 年 10 月中級 第 2 題
簡潔題意
兩張 \(R \times C\) 的灰階照片 \(A\)、\(B\)(\(R, C \le 200\),灰階值 \(0 \sim 255\))。兩張可以各自順時針轉 \(0^\circ\)、\(90^\circ\)、\(180^\circ\) 或 \(270^\circ\);轉完大小不同,相似度是 \(0\%\);大小相同時,若相同位置灰階值相同的格子有 \(S\) 個,相似度是 \(\left\lfloor \dfrac{100S}{RC} \right\rfloor\%\)。輸出最高的相似度。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(60\) 分):\(R = 1\)。
- 子題組 2(\(40\) 分):無額外限制。
先想清楚:只要轉 \(B\)
兩張照片轉同一個角度,對到的格子還是同一對,相似度不變。所以「\(A\) 轉 \(x\) 度、\(B\) 轉 \(y\) 度」和「\(A\) 不轉、\(B\) 多轉 \(y - x\) 度」一樣——只要讓 \(B\) 轉 \(0^\circ\)、\(90^\circ\)、\(180^\circ\)、\(270^\circ\) 四種,各算一次相似度,取最大的。
轉 \(90^\circ\) 或 \(270^\circ\) 會讓大小從 \(R \times C\) 變成 \(C \times R\),所以照片不是正方形時,這兩種一定是 \(0\%\)。
相似度用整數算:100 * same / (R * C) 的整數除法本身就是無條件捨去(2.6)。照片最多 \(40000\) 格,分子最多是 \(400\) 萬,int 放得下。
先拿下子題組 1(60 分):只剩不轉和左右顛倒
只有一列的照片轉 \(180^\circ\) 就是左右顛倒:\(B\) 的第 \(j\) 格換成第 \(C - 1 - j\) 格。轉 \(90^\circ\)、\(270^\circ\) 會變成 \(C \times 1\),除了 \(C = 1\)(那時四種轉法都一樣)之外都是 \(0\%\)。所以只要比兩種。
#include <bits/stdc++.h>
using namespace std;
int A[200], B[200];
int main() {
int R, C;
cin >> R >> C; // 子題組 1 保證 R = 1
for (int j = 0; j < C; j++) cin >> A[j];
for (int j = 0; j < C; j++) cin >> B[j];
int same0 = 0, same180 = 0;
for (int j = 0; j < C; j++) {
if (A[j] == B[j]) same0++; // 不轉
if (A[j] == B[C - 1 - j]) same180++; // B 轉 180 度=左右顛倒
}
int best = max(same0, same180);
cout << 100 * best / C << "%" << endl;
}
範例是 \(6 \times 5\),這個版本對範例會 WA 是正常的;它對子題組 1 的 \(12\) 筆全對,穩拿 \(60\) 分。
從 60 分到 100 分:寫一個「順時針轉 \(90^\circ\)」的函式
順時針旋轉的公式:\(R \times C\) 的舊圖第 \(i\) 列第 \(j\) 欄,搬到新圖的第 \(j\) 列、第 \(R - 1 - i\) 欄。新圖大小是 \(C \times R\),要另外開一張新的表,不能在原地轉。把它寫成函式 rotateB,每比完一次就把 \(B\) 轉一次,迴圈跑四次正好比到 \(0^\circ\)、\(90^\circ\)、\(180^\circ\)、\(270^\circ\)。大小和 \(A\) 不同的那幾次直接跳過(相似度 \(0\%\))。
照片用全域的二維陣列存(6.9),rotateB 直接改全域的 B:先把轉好的圖寫進另一張表 tmp,再抄回 B。\(B\) 轉完列數、欄數會對調,所以另外用 rowsB、colsB 記它現在的大小。四次比對加四次旋轉(每次旋轉寫一遍 tmp、再抄回一遍),總共不到 \(5 \times 10^5\) 次運算。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 205; // R、C 都不超過 200
int A[MAX_N][MAX_N], B[MAX_N][MAX_N], tmp[MAX_N][MAX_N];
int rowsB, colsB; // B 現在的大小:轉 90 度之後列數、欄數會對調
void rotateB() { // B 順時針轉 90 度:舊圖 (i, j) 搬到新圖 (j, rowsB - 1 - i)
for (int i = 0; i < rowsB; i++) {
for (int j = 0; j < colsB; j++) {
tmp[j][rowsB - 1 - i] = B[i][j];
}
}
swap(rowsB, colsB); // 新圖是 colsB 列、rowsB 欄
for (int i = 0; i < rowsB; i++) { // 轉好的圖抄回 B
for (int j = 0; j < colsB; j++) {
B[i][j] = tmp[i][j];
}
}
}
int main() {
int R, C;
cin >> R >> C;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) cin >> A[i][j];
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) cin >> B[i][j];
}
rowsB = R;
colsB = C;
int best = 0;
for (int t = 0; t < 4; t++) { // B 依序轉 0、90、180、270 度
if (rowsB == R && colsB == C) { // 大小不同=0%,不用比
int same = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (A[i][j] == B[i][j]) same++;
}
}
best = max(best, 100 * same / (R * C));
}
rotateB();
}
cout << best << "%" << endl;
}
測過再交:範例的答案是轉 \(180^\circ\)
範例不是正方形,答案又剛好是轉 \(180^\circ\):「不轉」「轉 \(90^\circ\)」「轉 \(270^\circ\)」「無條件捨去」全部沒測到。下面三種錯法範例都會過(見常犯錯誤),自己補這幾筆:
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 3/1 2 3/1 2 4 |
66% |
不轉就是最好的;\(200 / 3\) 無條件捨去 |
2 2/1 2/3 4/3 1/4 2 |
100% |
\(B\) 要轉 \(270^\circ\) 才對得上 |
2 2/1 2/3 4/2 4/1 3 |
100% |
\(B\) 要轉 \(90^\circ\) 才對得上 |
2 2/1 2/3 4/2 1/4 3 |
50% |
\(B\) 是 \(A\) 左右翻轉,翻轉不是旋轉 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 只試了轉過的,忘了不轉也是一種:範例全過,自測表第 1 列印
33%;本站 \(20\) 筆掛 \(3\) 筆。 - 正方形時沒試 \(90^\circ\) 和 \(270^\circ\),只比不轉和 \(180^\circ\):範例不是正方形,所以全過;自測表第 2、3 列都印
0%,本站 \(20\) 筆掛 \(3\) 筆。只漏了 \(270^\circ\) 也會掛 \(2\) 筆,自測表第 2 列抓得到。 - 把左右翻轉也當成一種轉法:範例全過,自測表第 4 列印
100%;本站 \(20\) 筆掛 \(1\) 筆。