LED 螢幕偏移還原 (APCS 2026-06 中級)

2.0s 256M

有一塊 \(N\) 列、\(M\) 欄的 LED 螢幕,每一格顯示一個字元:. 或大寫英文字母。螢幕正常時應該顯示畫面 \(a\),可是設定出了錯,整個畫面循環偏移,變成了畫面 \(b\)。

畫面有兩種移動方式:

  • 向右移動一次:每一列的字元都往右移一格,原本在最右邊一欄的字元,繞回同一列的最左邊。
  • 向下移動一次:每一欄的字元都往下移一格,原本在最下面一列的字元,繞回同一欄的最上面。

下圖是一個 \(3\) 列 \(4\) 欄的畫面:上面一排是把它向右移動一次,下面一排是把它向下移動一次,淺綠色的格子是從另一邊繞回來的字元,. 畫成灰色小點。例如第一列 AB.C 向右移動一次會變成 CAB.。

3 列 4 欄的畫面 AB.C、.DE.、F..G。向右移動一次變成 CAB.、..DE、GF..,最右邊一欄 C、.、G 繞到最左邊;向下移動一次變成 F..G、AB.C、.DE.,最下面一列 F..G 繞到最上面

請算出畫面 \(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\) 一樣。淺綠色的格子是這一步繞回來的字元。

範例 2:b 是 K.LIJ、.OPMN、.CDAB、FGHE.;向右移動 2 次變成 IJK.L、MN.OP、AB.CD、E.FGH;再向下移動 2 次變成 AB.CD、E.FGH、IJK.L、MN.OP,和 a 相同

這筆範例只有 \((r, d) = (2, 2)\) 這一組能把 \(b\) 變回 \(a\),所以輸出 2 2。

題目來源

APCS 2026 年 6 月中級實作題第 3 題。

官方未公布題本,題敘參考 APCS Simulation 整理,細節可能與正式試題有出入。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器(per 帳號 / 題目 / 語言)。
  • 提交 — 把程式碼交給 judge 評測,回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB (約 100 萬字元)
  • 自訂測試每人約 3 秒 1 次 (範例測試 1 秒 1 次)
  • 自訂測試有 15 秒 牆鐘上限;範例測試和正式評測一樣,照題目的時間限制
  • 互動題不提供自訂測試(無法模擬與 judge 互動)。
  • 提交評測本身沒有 rate limit,但同題短時間內多次提交會被視為刷分。