字謎盤面產生器 題解|APCS 2026 年 10 月中級 第 2 題


簡潔題意

\(R \times C\) 的盤面,\((r, c)\) 是第 \(r\) 列第 \(c\) 欄(都從 \(1\) 開始),一開始全空。依序處理 \(K\) 個大寫英文單字,每個單字從起點 \((r, c)\) 往右(\(D = 0\))或往下(\(D = 1\))一格放一個字母。單字有字母超出盤面,或經過的某一格已經有不同的字母(比的是格子裡實際的字母,包括輸出時顯示成 _ 的),就整個不放;字母相同就共用那一格。全部處理完輸出盤面:沒有被任何放上的單字經過的格子印 *;是某個放上的單字的第一個或最後一個字母的格子印那個字母;其他經過的格子印 _(\(1 \le R, C \le 200\)、\(1 \le K \le 100\),單字長 \(2\)~\(200\))。

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

  • 子題組 1(\(60\) 分):\(R = 1\),且每個單字的 \(D = 0\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):每一格記兩件事,先檢查、再放

子題組 1 的盤面只有一列,單字都從第 \(c\) 欄往右放。單字的長度事先不知道,用 string 讀進來:w.size() 是字母個數 \(L\),w[k] 是第 \(k + 1\) 個字母,放在第 \(c + k\) 欄(\(k\) 從 \(0\) 數到 \(L - 1\))。

每一格要記兩件事,各開一個陣列,欄號從 \(1\) 用起、多開一格(語法書 6.3):

  • letter[c]:格子裡實際的字母。開在全域,一開始全是 \(0\)(語法書 6.5),\(0\) 就代表空格。判斷衝突拿它比——顯示成 _ 的格子,底下也有字母。
  • isEnd[c]:有沒有當過某個放上的單字的第一個或最後一個字母。它只會從 false 變成 true,和單字放的先後無關。

輸出時才決定每一格印什麼:letter 是 \(0\) 印 *,isEnd 是 true 印字母,其他印 _。顯示不要在放單字的時候就寫死:一格會不會變成首尾,要等後面的單字都放完才知道。

每個單字照順序做三步:

  1. 出界:起點在盤面內、單字只往右放,所以只要看最後一個字母——它在第 \(c + L - 1\) 欄,大於 \(C\) 就跳過;剛好等於 \(C\) 是放得下的。這一步要最先做,後面的迴圈才不會碰到陣列外面的格子。
  2. 衝突:逐格看,有一格「有字母,而且和 w[k] 不一樣」就整個不放。這是「是不是每一格都沒問題」的旗標(語法書 4.10):ok 先設 true,碰到衝突改成 false 再 break。break 只跳出檢查的迴圈,所以迴圈結束後再看 ok,是 false 才 continue 跳過這個單字。
  3. 放:前兩步都過了,才把字母寫進 letter,第一格、最後一格標 isEnd。

檢查和放要分成兩個迴圈,全部檢查完才開始放:題目要「整個不放」,寫上去的字母收不回來。

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

const int MAX_C = 200;

char letter[MAX_C + 1];   // letter[c]:第 c 欄實際的字母,0 表示空格(從 1 用起)
bool isEnd[MAX_C + 1];    // isEnd[c]:有沒有當過某個放上的單字的第一個或最後一個字母

int main() {
    int R, C, K;
    cin >> R >> C >> K;                     // 子題組 1 保證 R = 1:盤面只有一列
    for (int i = 0; i < K; i++) {
        int r, c, D;
        string w;
        cin >> r >> c >> D >> w;            // 子題組 1 保證 r = 1、D = 0:只用得到 c
        int L = w.size();

        if (c + L - 1 > C) continue;        // 1. 最後一個字母超出第 C 欄:整個不放

        bool ok = true;                     // 2. 每一格都沒有衝突嗎?
        for (int k = 0; k < L; k++) {
            char x = letter[c + k];
            if (x != 0 && x != w[k]) {      // 有字母,而且不一樣
                ok = false;
                break;
            }
        }
        if (!ok) continue;                  //    有衝突:整個不放

        for (int k = 0; k < L; k++) letter[c + k] = w[k];   // 3. 放
        isEnd[c] = true;                    // 第一個字母
        isEnd[c + L - 1] = true;            // 最後一個字母
    }

    for (int c = 1; c <= C; c++) {
        if (letter[c] == 0) cout << '*';
        else if (isEnd[c]) cout << letter[c];
        else cout << '_';
    }
    cout << '\n';
    return 0;
}

這份程式交上去,範例 2 會 WA——它有 \(5\) 列,這份程式只印一列。這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手;想自己驗,用範例 1 和自測表的第 1~4 筆(都只有一列)。

從 60 分到 100 分:換成二維,往下也要檢查出界

盤面變成 \(R\) 列 \(C\) 欄,兩張表換成二維的 letter[r][c]、isEnd[r][c],一樣開在全域,列和欄都從 \(1\) 用起(語法書 6.9)。

往右走一格是列不變、欄加 \(1\);往下走一格是列加 \(1\)、欄不變。把走一格時列和欄的變化記成 dr、dc:往右是 dr = 0、dc = 1,往下是 dr = 1、dc = 0。w[k] 從起點走了 \(k\) 格,放在第 r + k * dr 列、第 c + k * dc 欄——子題組 1 的第 \(c + k\) 欄就是往右的情形。

三個步驟原封不動,格子換成二維就好。出界一樣只看最後一個字母,它在第 er 列第 ec 欄(er = r + (L - 1) * dr、ec = c + (L - 1) * dc)。列和欄都要檢查:往右的單字會超出欄,往下的單字會超出列,寫成 er > R || ec > C 一次擋掉。

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

const int MAX_R = 200;
const int MAX_C = 200;

char letter[MAX_R + 1][MAX_C + 1];   // letter[r][c]:第 r 列第 c 欄實際的字母,0 表示空格(都從 1 用起)
bool isEnd[MAX_R + 1][MAX_C + 1];    // isEnd[r][c]:有沒有當過某個放上的單字的第一個或最後一個字母

int main() {
    int R, C, K;
    cin >> R >> C >> K;
    for (int i = 0; i < K; i++) {
        int r, c, D;
        string w;
        cin >> r >> c >> D >> w;
        int L = w.size();
        int dr = 0, dc = 1;                 // D = 0:往右,欄加 1
        if (D == 1) {                       // D = 1:往下,列加 1
            dr = 1;
            dc = 0;
        }

        int er = r + (L - 1) * dr;          // 最後一個字母在第 er 列第 ec 欄
        int ec = c + (L - 1) * dc;
        if (er > R || ec > C) continue;     // 1. 超出盤面:整個不放

        bool ok = true;                     // 2. 每一格都沒有衝突嗎?
        for (int k = 0; k < L; k++) {
            char x = letter[r + k * dr][c + k * dc];
            if (x != 0 && x != w[k]) {      // 有字母,而且不一樣
                ok = false;
                break;
            }
        }
        if (!ok) continue;                  //    有衝突:整個不放

        for (int k = 0; k < L; k++) letter[r + k * dr][c + k * dc] = w[k];   // 3. 放
        isEnd[r][c] = true;                 // 第一個字母
        isEnd[er][ec] = true;               // 最後一個字母
    }

    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            if (letter[r][c] == 0) cout << '*';
            else if (isEnd[r][c]) cout << letter[r][c];
            else cout << '_';
        }
        cout << '\n';
    }
    return 0;
}

跟子題組版比,換掉的只有三件事:表變成二維(輸出也跟著印 \(R\) 列),字母的位置改用 dr 和 dc 算,出界多檢查了列。每個單字最多 \(200\) 個字母,檢查、放各走一次,\(100\) 個單字加起來最多 \(100 \times 200 \times 2 = 4 \times 10^4\) 步;輸出 \(200 \times 200 = 4 \times 10^4\) 格,一下就跑完。

測過再交:範例沒有往下出界,也沒有首尾落在別人的中間

範例 2 有往右出界、剛好貼齊、共用,也有單字撞上顯示成 _ 的格子,可是它有 \(5\) 列,子題組版拿它驗不了;範例 1 的兩個單字互不相干。兩個範例都沒有往下超出盤面的單字,也沒有哪一格是某個單字的中間、又是另一個單字的首尾(題目敘述的 PAPER、UP 才有)。自己補上這幾種,前四筆只有一列,子題組版也能驗:

輸入 正確輸出 這一筆在測什麼
1 5 2 / 1 3 0 BIRD / 1 4 0 IT ***IT BIRD 的 D 超出第 \(5\) 欄,整個不放;IT 剛好放到第 \(5\) 欄
1 5 2 / 1 1 0 PLANE / 1 2 0 LON P___E LON 的 O 撞到 PLANE 的 A:那一格顯示 _,底下還是 A,整個不放
1 5 2 / 1 1 0 PLANE / 1 2 0 LAN PL_NE LAN 的三個字母都和 PLANE 相同,共用;LAN 的首尾落在 PLANE 的中間,顯示字母
1 5 2 / 1 2 0 LAN / 1 1 0 PLANE PL_NE 和上一筆同樣兩個單字、順序對調:PLANE 的中間經過 LAN 的首尾,那兩格還是顯示字母
2 3 2 / 1 1 1 GO / 1 2 1 TWO G** / O** 往下放:GO 剛好放到第 \(2\) 列;TWO 的 O 超出第 \(2\) 列,整個不放
用程式造:\(200 \times 200\) 的盤面,從 \((1, 200)\) 往下放 \(200\) 個 A,再從 \((200, 1)\) 往右放 \(200\) 個 A 第 \(1\) 列:\(199\) 個 *、A;第 \(2\)~\(199\) 列:\(199\) 個 *、_;第 \(200\) 列:A、\(198\) 個 _、A 最大的盤面、最長的單字:兩個單字都剛好貼齊盤面的邊,共用右下角

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

常犯錯誤
  • 檢查和放寫在同一個迴圈(比一格、寫一格,首尾也跟著標,撞到才停):範例 2 的 TEA 在 \((2, 2)\) 留下 T,第 2 列印 *T_**。
  • 檢查到衝突只寫 continue 或 break(沒有旗標):單字照樣整個放上去——範例 2 第 2、4 列印 *T_**、*A_**。
  • 只存顯示出來的盤面(*、_、字母):_ 當成空的,範例 2 的 TEA 會放上去,第 4 列印 *A_**;_ 當成和誰都不同,SALES 放不上去,第 3 列印 *__**。
  • 出界沒檢查,或寫成 c + L > C(剛好放到第 \(C\) 欄也算出界):範例 1 都過,自測表第 1 筆分別印 **B__、*****。
  • 從子題組版改過來,只檢查了欄:兩個範例都過,自測表第 5 筆印 GT*/O_*。
  • 還沒確定放得上就先標首尾:兩個範例都過,自測表第 2 筆印 PL_NE——沒放上去的 LON 留下了首尾。
  • 放單字的時候就決定顯示什麼(另外開一張存 *、_、字母的表):兩個範例都過。每次直接蓋掉,自測表第 4 筆印 P___E;只在空格時寫,第 3 筆印 P___E。