Editorial for 卡牌遊戲 (APCS 2023-10 中級)

簡潔題意

\(n\) 列 \(m\) 欄的表格，每格一張卡牌，每個數值恰好出現兩次。同數值的兩張牌若在同一列或同一欄、而且它們之間沒有任何還沒移除的牌，就可以把兩張一起移除、得到該數值的分數（移除後變空格，空格不擋牌）。可以反覆操作、順序自選，求最多能得幾分（\(1 \le n \le 20\)、\(1 \le m \le 40\)、數值 \(0 \sim 1000\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(60\) 分）：\(n = 1\)。
  • 子題組 2（\(40\) 分）：無額外限制。

先拿下子題組 1（60 分）：一列牌，反覆從左掃到右

先想清楚一件事：該不該先拿哪一對？不用想。移除牌只會讓格子從「有牌」變「空格」——別的牌之間只會多出空格，不會多出障礙。原本能拿的一對，之後永遠還能拿；原本被擋住的，之後只可能變成能拿。所以有牌可拿就拿，順序無所謂，最後拿到的一定最多。

\(n = 1\) 只有一列，「中間沒有牌」就是「這張牌往右掃到的第一張牌」（13.5：往一個方向看，最先撞到的是誰）。從左往右掃一遍，記住 last＝上一張還在的牌在哪：遇到一張牌，跟 card[last] 同數值就是一對——中間必定全是空格——兩張都拿掉、last 歸零重新找；不同就把 last 換成這一張。

拿掉的牌用 EMPTY = -1 標記——不能用 \(0\)，\(0\) 是題目允許的卡牌數值。

一趟掃完不一定就結束：5 3 3 5 第一趟只拿得到 \(3\)（掃到第二個 \(5\) 時，上一張還在的牌是 \(3\)），要等 \(3\) 拿掉、第二趟才輪到 \(5\)。所以反覆掃，直到某一趟一張都沒拿到為止：

#include <iostream>
using namespace std;

const int MAX_M = 40;
const int EMPTY = -1;   // 拿掉的牌用 -1 標記（卡牌數值 0~1000，0 是合法數值，不能拿來當空格）

int main() {
    int n, m;
    cin >> n >> m;                 // 子題組 1 保證 n = 1：只有一列
    int card[MAX_M];
    for (int j = 0; j < m; j++) {
        cin >> card[j];
    }

    int score = 0;
    bool changed = true;
    while (changed) {              // 反覆掃，直到一整趟都沒有牌可拿
        changed = false;
        int last = -1;             // 上一張還在的牌在哪；-1 代表還沒遇到牌
        for (int j = 0; j < m; j++) {
            if (card[j] == EMPTY) {
                continue;          // 空格不擋牌，跳過就好
            }
            if (last != -1 && card[j] == card[last]) {   // 和上一張牌同數值＝中間全是空格
                score += card[j];
                card[j] = EMPTY;
                card[last] = EMPTY;
                last = -1;         // 兩張都拿掉了，重新找下一張
                changed = true;
            } else {
                last = j;
            }
        }
    }
    cout << score << '\n';
    return 0;
}

兩個地方別踩：

  • 空格要跳過，但不能拿去更新 last——空格不是牌。把 last 指到空格上，5 _ 5 就永遠配不起來。
  • changed 看的是「有沒有拿掉牌」，不是分數有沒有變：一對 \(0\) 拿掉得 \(0\) 分，但它們讓出來的空格可能讓別的牌接上。

這份程式交上去，範例 2 和 \(n > 1\) 的測資會 WA——這是正常的，逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。

從 60 分到 100 分：同一趟掃描，換個方向再跑一次

\(n > 1\) 之後，同一欄的牌也能配對。做法一模一樣：每一列從左往右掃一趟、每一欄從上往下掃一趟，兩種掃描合成一輪，反覆到一整輪都沒拿到牌為止。

列掃描和欄掃描的程式碼幾乎一字不差——差別只在「下一格往哪走」。這種能預料的重複，就包成一個函式、把會換的部分變成參數：scan_line(r, c, dr, dc) 從 \((r, c)\) 出發、沿方向 \((dr, dc)\) 一路掃到出界（就是 13.5 的射線）；列掃描是 scan_line(i, 0, 0, 1)、欄掃描是 scan_line(0, j, 1, 0)。

#include <iostream>
using namespace std;

const int MAX_N = 20;
const int MAX_M = 40;
const int EMPTY = -1;   // 拿掉的牌用 -1 標記（卡牌數值 0~1000，0 是合法數值，不能拿來當空格）

int n, m;
int card[MAX_N][MAX_M];
int score = 0;

// 從 (r, c) 出發、沿方向 (dr, dc) 一路掃到出界：
// 遇到的牌和「上一張還在的牌」同數值就把兩張拿掉。回傳這一趟有沒有拿掉任何牌
bool scan_line(int r, int c, int dr, int dc) {
    bool removed_any = false;
    int last_r = -1, last_c = -1;              // 上一張還在的牌在哪；-1 代表還沒遇到牌
    while (r >= 0 && r < n && c >= 0 && c < m) {
        if (card[r][c] != EMPTY) {             // 空格不擋牌，跳過就好
            if (last_r != -1 && card[r][c] == card[last_r][last_c]) {   // 和上一張牌同數值＝中間全是空格
                score += card[r][c];
                card[r][c] = EMPTY;
                card[last_r][last_c] = EMPTY;
                last_r = -1;
                last_c = -1;                   // 兩張都拿掉了，重新找下一張
                removed_any = true;
            } else {
                last_r = r;
                last_c = c;
            }
        }
        r += dr;
        c += dc;
    }
    return removed_any;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> card[i][j];
        }
    }

    bool changed = true;
    while (changed) {                          // 反覆做，直到一整輪都沒有牌可拿
        changed = false;
        for (int i = 0; i < n; i++) {          // 每一列：從最左邊往右掃
            if (scan_line(i, 0, 0, 1)) {
                changed = true;
            }
        }
        for (int j = 0; j < m; j++) {          // 每一欄：從最上面往下掃
            if (scan_line(0, j, 1, 0)) {
                changed = true;
            }
        }
    }
    cout << score << '\n';
    return 0;
}

跟子題版比，換掉的東西：

  • 一列變一張表：card[MAX_N][MAX_M]，last 也變成一組座標 (last_r, last_c)。
  • 掃描包成 scan_line：card、n、m、score 放在全域讓函式直接用；函式回傳「這一趟有沒有拿掉牌」，主程式拿它來決定 changed。
  • 多了欄掃描：就是同一個函式換個方向再叫一次。

會不會太慢？沒拿到牌的那一輪就是最後一輪，所以前面每一輪至少拿掉一對——牌最多 \(20 \times 40 = 800\) 張、\(400\) 對，最多 \(400\) 輪；每輪列掃描、欄掃描各把整張表看過一次（\(1600\) 格），總共不到一百萬次操作。分數最大 \(400 \times 1000 = 400000\)，int 綽綽有餘。

測過再交：範例沒讓 0 分的一對真的被拿掉

範例 2 其實把「要掃好幾輪」「靠欄才接得上」「隔著空格配對」都考到了，只是 \(29\) 分要手算並不輕鬆，錯了也不容易看出是哪一段出問題；範例 1 那對 \(0\) 則一直被 \(2\) 擋著——「\(0\) 分的一對真的被拿掉」在兩個範例裡都沒發生過。用手算得動的最小測資自己造，一筆只驗一件事：

輸入 正確輸出 這一筆在測什麼
1 4 ／ 1 0 0 1 1 一對 \(0\) 拿掉得 \(0\) 分，但拿掉之後兩張 \(1\) 才接得上——changed 只看分數的程式會印 0
1 4 ／ 5 3 3 5 8 一趟不夠：第一趟只拿得到 \(3\)，第二趟才輪到 \(5\)——只掃一趟的程式印 3
3 2 ／ 7 1 ／ 2 2 ／ 7 1 10 先靠列拿掉 \(2\)，兩對 \(7\)、\(1\) 才靠欄接上——只掃列的程式印 2
1 4 ／ 1 2 1 2 0 交錯排列、一張都拿不掉：確認程式會正常結束、印 0

四筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 用 \(0\) 當空格標記：數值 \(0\) 的牌一讀進來就被當成空格。範例 1 印 10（該印 8）、範例 2 印 31（該印 29）。
  • changed 只在分數增加時才設：拿掉一對 \(0\) 不算「有變化」，該輪之後就停了——兩個範例都會過；自測表第 1 列印 0。
  • 只掃一輪、沒有外層 while：範例 1 過、範例 2 印 23（該印 29）。
  • 只掃列、沒掃欄：範例 1 過（它只有一列）、範例 2 印 5。
  • 空格沒跳過、當成一張牌：兩個相鄰的空格「數值相同」會被當成一對一直拿——分數一直加 \(-1\)，兩個範例都跑不完。
  • 把空格也拿去更新 last：空格擋住了不該擋的牌，5 _ 5 永遠配不起來。範例 1 過、範例 2 印 12。