LED 螢幕偏移還原 (APCS 2026-06 中級)
2.0s 256M有一塊 \(N\) 列、\(M\) 欄的 LED 螢幕,每一格顯示一個字元:. 或大寫英文字母。螢幕正常時應該顯示畫面 \(a\),可是設定出了錯,整個畫面循環偏移,變成了畫面 \(b\)。
畫面有兩種移動方式:
- 向右移動一次:每一列的字元都往右移一格,原本在最右邊一欄的字元,繞回同一列的最左邊。
- 向下移動一次:每一欄的字元都往下移一格,原本在最下面一列的字元,繞回同一欄的最上面。
下圖是一個 \(3\) 列 \(4\) 欄的畫面:上面一排是把它向右移動一次,下面一排是把它向下移動一次,淺綠色的格子是從另一邊繞回來的字元,. 畫成灰色小點。例如第一列 AB.C 向右移動一次會變成 CAB.。
請算出畫面 \(b\) 要先向右移動 \(r\) 次、再向下移動 \(d\) 次(\(0 \le r < M\),\(0 \le d < N\)),才能變回正常畫面 \(a\)。
可能有好幾組 \((r, d)\) 都可以,這時先選總移動次數 \(r + d\) 最少的;總次數也一樣,再選向下移動次數 \(d\) 最少的。例如 \((r, d) = (1, 2)\) 和 \((3, 0)\) 都可以把 \(b\) 變回 \(a\) 時,兩組都移動 \(3\) 次,要選 \(d\) 比較少的 \((3, 0)\)。
輸入格式
第一行有兩個正整數 \(N\) 和 \(M\),代表螢幕有 \(N\) 列、\(M\) 欄。
接下來 \(N\) 行是正常畫面 \(a\),再接下來 \(N\) 行是偏移後的畫面 \(b\)。每一行恰好有 \(M\) 個字元,由左而右依序是那一列每一欄的字元,字元之間沒有空白。
限制
- \(1 \le N \le 50\)
- \(1 \le M \le 50\)
- 畫面上的字元只有
.和大寫英文字母A~Z。 - 保證 \(b\) 可以經過向右、向下移動變回 \(a\)。
輸出格式
輸出一行,包含兩個整數 \(r\) 和 \(d\),以一個空白隔開:先輸出向右移動的次數,再輸出向下移動的次數。
評分說明
每一筆測試資料的執行時間限制均為 \(2\) 秒,依正確通過的測試資料筆數給分。
範例輸入 1
3 3
.B.
ADA
.C.
..B
AAD
..C
範例輸出 1
2 0
範例解釋 1
把 \(b\) 向右移動 \(1\) 次、\(2\) 次,畫面依序變成:
B..
DAA
C..
.B.
ADA
.C.
向右移動 \(2\) 次之後就和 \(a\) 一樣,不用向下移動。這筆範例只有 \((r, d) = (2, 0)\) 這一組能把 \(b\) 變回 \(a\),所以輸出 2 0。
範例輸入 2
4 5
AB.CD
E.FGH
IJK.L
MN.OP
K.LIJ
.OPMN
.CDAB
FGHE.
範例輸出 2
2 2
範例解釋 2
下圖從左上角的 \(b\) 開始,照順時針方向看:\(b\) 向右移動 \(2\) 次,最右邊兩欄繞到最左邊;再向下移動 \(2\) 次,最下面兩列繞到最上面,就和左下角的 \(a\) 一樣。淺綠色的格子是這一步繞回來的字元。
這筆範例只有 \((r, d) = (2, 2)\) 這一組能把 \(b\) 變回 \(a\),所以輸出 2 2。
題目來源
APCS 2026 年 6 月中級實作題第 3 題。
官方未公布題本,題敘參考 APCS Simulation 整理,細節可能與正式試題有出入。