航空拍照圖 (APCS 2025-10 中級)
1.0s 256M某地區在不同時間由飛機拍攝了兩張灰階空拍照片。每張照片可表示為一個 \(R\) 列、\(C\) 欄的二維陣列;每個元素是該位置的灰階值。
為了比較兩張照片,你可以分別將每張照片順時針旋轉 \(0^\circ\)、\(90^\circ\)、\(180^\circ\) 或 \(270^\circ\)。
若旋轉後兩張照片的列數或欄數不同,這組旋轉方式的相似度為 \(0\%\)。 否則,設兩張照片在相同位置具有相同灰階值的格子數為 \(S\),則相似度為
\[\left\lfloor \frac{100S}{RC} \right\rfloor\%.\]請求出所有旋轉方式中最高的相似度。
輸入格式
第一列包含兩個整數 \(R\)、\(C\),表示每張照片的列數與欄數。
接下來 \(R\) 列,每列包含 \(C\) 個整數,表示照片 A。
再接下來 \(R\) 列,每列包含 \(C\) 個整數,表示照片 B。
限制
- \(1\le R,C\le200\)
- \(0\le A_{i,j},B_{i,j}\le255\)
輸出格式
輸出最高相似度的整數值,並在後方接上一個百分比符號 %。
評分說明
每一筆測試資料的執行時間限制均為 \(1\) 秒,依正確通過的測試資料筆數給分。其中:
| 子題組 | 分數 | 額外限制 |
|---|---|---|
| 1 | 60 | \(R=1\) |
| 2 | 40 | 無額外限制 |
範例輸入
6 5
0 1 1 1 1
0 2 2 2 2
0 3 3 3 3
0 4 4 4 4
0 5 5 5 5
0 6 6 6 6
6 6 6 6 6
5 5 5 5 5
4 4 4 4 4
7 7 7 7 0
8 8 8 8 0
9 9 9 9 0
範例輸出
50%
範例解釋
將照片 B 旋轉 \(180^\circ\) 後,共有 \(15\) 個位置與照片 A 的灰階值相同。 照片共有 \(6\times5=30\) 個位置,因此相似度為 \(\left\lfloor100\times15/30\right\rfloor=50\%\),且其他旋轉方式 不會得到更高的相似度。
題目來源
APCS 2025 年 10 月中級實作題第 2 題。
題敘參考 ZeroJudge r489「航空拍照圖」 整理,細節可能與正式試題有出入。