字謎盤面產生器 題解|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 印字母,其他印 _。顯示不要在放單字的時候就寫死:一格會不會變成首尾,要等後面的單字都放完才知道。
每個單字照順序做三步:
- 出界:起點在盤面內、單字只往右放,所以只要看最後一個字母——它在第 \(c + L - 1\) 欄,大於 \(C\) 就跳過;剛好等於 \(C\) 是放得下的。這一步要最先做,後面的迴圈才不會碰到陣列外面的格子。
- 衝突:逐格看,有一格「有字母,而且和
w[k]不一樣」就整個不放。這是「是不是每一格都沒問題」的旗標(語法書 4.10):ok先設true,碰到衝突改成false再break。break只跳出檢查的迴圈,所以迴圈結束後再看ok,是false才continue跳過這個單字。 - 放:前兩步都過了,才把字母寫進
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。