LED 螢幕偏移還原 題解|APCS 2026 年 6 月中級 第 3 題


簡潔題意

\(N \times M\) 的畫面 \(a\)、\(b\)(\(N, M \le 50\)),每格是 . 或大寫英文字母。向右移動一次:每一列往右一格,最右邊一欄繞回最左邊;向下移動一次:每一欄往下一格,最下面一列繞回最上面。求 \(b\) 先向右移動 \(r\) 次、再向下移動 \(d\) 次(\(0 \le r < M\)、\(0 \le d < N\))會變回 \(a\) 的 \((r, d)\);有好幾組時選 \(r + d\) 最小的,再一樣選 \(d\) 最小的。保證有解。(APCS 逐筆給分。)

每一組都試:每一格是從哪裡搬來的

\(r\) 只有 \(M\) 種、\(d\) 只有 \(N\) 種,最多 \(50 \times 50 = 2500\) 組,全部試一遍。

每一組不用真的把畫面搬來搬去,只要知道搬完之後每一格放的是 \(b\) 的哪一格(列、欄都從 \(0\) 數起):

  • 向右移動 \(r\) 次:第 \(j\) 欄放的是原本第 \(j - r\) 欄的字元;\(j - r\) 是負的,表示從右邊繞過來,要加 \(M\)。
  • 向下移動 \(d\) 次:第 \(i\) 列放的是原本第 \(i - d\) 列;是負的就加 \(N\)。

所以搬完之後的第 \(i\) 列第 \(j\) 欄,就是 \(b\) 的第 \((i - d + N) \bmod N\) 列、第 \((j - r + M) \bmod M\) 欄。每一格都和 \(a\) 一樣,這一組就成立。C++ 的 % 遇到負數會得到負數(2.6:-1 % 3 是 -1),所以先加 \(N\)、\(M\) 再取餘數。

拿範例 1 對一下:\(r = 2\)、\(d = 0\) 時,\(a\) 第 \(0\) 列第 \(1\) 欄的 B,要等於 \(b\) 第 \(0\) 列第 \((1 - 2 + 3) \bmod 3\) 欄,也就是第 \(2\) 欄。\(b\) 的第 \(0\) 列是 ..B,第 \(2\) 欄正好是 B。

畫面的每一列存成一個 string,a[i][j] 就是第 \(i\) 列第 \(j\) 欄的字元。

照規則挑答案:不能找到第一組就停

外層跑 \(d\)、內層跑 \(r\),都由小到大;只在總次數 \(r + d\) 嚴格變小時才換:

  • 總次數比較少的,一定換得上來。
  • 總次數一樣的,\(d\) 比較小的在外層先被找到,後面的換不掉它。

找到第一組就停是錯的:外層跑 \(d\) 時第一組是 \(d\) 最小的,可是它的總次數不一定最小(自測表第 2 列)。

比對時一對不上就停,換下一組(迴圈條件加上 && same)。最多 \(2500\) 組、每組最多比 \(2500\) 格,共 \(6.25 \times 10^6\) 次比較,很快就跑完。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 55;       // N ≤ 50
string a[MAX_N], b[MAX_N];  // 每一列存成一個字串:a[i][j]=第 i 列第 j 欄

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < N; i++) cin >> b[i];

    int bestR = -1, bestD = -1;
    for (int d = 0; d < N; d++) {  // 外層 d、內層 r,都由小到大
        for (int r = 0; r < M; r++) {
            bool same = true;
            for (int i = 0; i < N && same; i++) {  // 一對不上就停
                for (int j = 0; j < M && same; j++) {
                    // b 向右 r 次、再向下 d 次之後,第 i 列第 j 欄放的是 b 的這一格
                    if (b[(i - d + N) % N][(j - r + M) % M] != a[i][j]) same = false;
                }
            }
            // 總次數嚴格變少才換:總次數一樣時,留下先找到的(d 比較小)
            if (same && (bestR == -1 || r + d < bestR + bestD)) {
                bestR = r;
                bestD = d;
            }
        }
    }
    cout << bestR << ' ' << bestD << '\n';
    return 0;
}

測過再交:兩個範例的解都只有一組

兩個範例都只有一組 \((r, d)\) 能把 \(b\) 變回 \(a\),完全測不到「好幾組時怎麼挑」。下面五種錯法範例都會過(見常犯錯誤),自己補這幾筆:

輸入 正確輸出 這一筆在測什麼
2 2/.A/A./A./.A 1 0 \((1, 0)\) 和 \((0, 1)\) 都可以,都只移動 \(1\) 次:選 \(d\) 小的
2 4/...A/.A../.A../...A 0 1 \((2, 0)\) 和 \((0, 1)\) 都可以:\(d\) 最小的要移動 \(2\) 次,\((0, 1)\) 只要 \(1\) 次
1 4/.A../..A. 3 0 只有一列;字母要從最右邊繞回最左邊
3 1/././A/./A/. 0 1 只有一欄:向下移動的方向
1 2/../.. 0 0 每一組都可以:不用移動

五筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 外層跑 \(d\),找到第一組就輸出:範例全過,自測表第 2 列印 2 0;本站 \(20\) 筆掛 \(4\) 筆。

  • 外層跑 \(r\)、內層跑 \(d\):總次數一樣時留下的是 \(r\) 小的。範例全過,自測表第 1 列印 0 1;本站 \(20\) 筆掛 \(5\) 筆。

  • 沒比總次數,後找到的蓋掉先找到的:範例全過,自測表第 5 列印 1 0;本站 \(20\) 筆掛 \(10\) 筆。

  • 向下的方向弄反(寫成 (i + d) % N):範例 1 不用向下、範例 2 向下 \(2\) 次剛好是 \(N\) 的一半,反過來也一樣,所以全過;自測表第 4 列印 0 2,本站 \(20\) 筆掛 \(14\) 筆。

  • 不繞回,只比移過去還在畫面裡的格子:範例全過,自測表第 3 列印 2 0;本站 \(20\) 筆掛 \(3\) 筆。

  • Python 一格一格比,對不上也不停:

    for i in range(N):
        for j in range(M):
            if b[(i - d) % N][(j - r) % M] != a[i][j]:
                ok = False
    

    答案都對、範例全過,但 \(50 \times 50\) 的畫面每一組都比完 \(2500\) 格,本站 \(20\) 筆有 \(4\) 筆超過 \(2\) 秒。只加 break 不一定夠:畫面全是同一個字元時每一組都成立,每一格都得比完。改成整列一起比,最慢的一筆約 \(0.12\) 秒:

    for i in range(N):
        row = b[(i - d) % N]                   # b 向下移 d 次之後的第 i 列
        if row[M - r:] + row[:M - r] != a[i]:  # 這一列再向右轉 r 次,整列一起比
            ok = False
            break