字謎盤面產生器 (APCS 2026-10 中級)

小美在寫一個產生字謎盤面的程式。盤面有 \(R\) 列 \(C\) 欄，由上而下第 \(r\) 列、由左而右第 \(c\) 欄的格子記為 \((r, c)\)，列、欄都從 \(1\) 開始編號。一開始每一格都是空的。

程式依序處理 \(K\) 個由大寫英文字母組成的單字。每個單字有一個起點 \((r, c)\) 和方向 \(D\)：\(D = 0\) 是水平，從起點往右放；\(D = 1\) 是垂直，從起點往下放。放一個單字，就是從起點開始沿著方向，一格放一個字母。例如從 \((2, 3)\) 水平放 CAT，C、A、T 會依序放在 \((2, 3)\)、\((2, 4)\)、\((2, 5)\)。

單字經過的格子如果已經有字母，而且和這個單字在那一格的字母相同，兩個單字就共用這一格。只要有下列任何一種情形，這個單字就整個不放，一個字母都不放，盤面維持原樣，接著處理下一個單字：

1. 單字有字母會超出盤面。
2. 單字經過的某一格已經有字母，而且和這個單字在那一格的字母不同。這裡比的是格子裡實際放的字母，也包括下面輸出時顯示成 _ 的格子。

全部處理完之後輸出盤面，每一格顯示一個字元：

• 沒有任何放上去的單字經過的格子，顯示 *。
• 是某個放上去的單字的第一個或最後一個字母的格子，顯示那個字母；即使這一格同時是另一個單字中間的字母，也顯示字母。
• 其他被經過的格子（只當過單字中間的字母），顯示 _。

舉例來說，在 \(2\) 列 \(5\) 欄的盤面上，先從 \((2, 1)\) 水平放 PAPER，再從 \((1, 3)\) 垂直放 UP。UP 的 P 落在 \((2, 3)\)，和 PAPER 在這一格的字母相同，所以 UP 放得上去。\((2, 3)\) 是 PAPER 中間的字母，但也是 UP 的最後一個字母，所以顯示 P；PAPER 的 A、E 只當過中間的字母，顯示 _。輸出的盤面是：

**U**
P_P_R

如果改成先放 UP、再放 PAPER，輸出也一樣。

輸入格式

第一行有三個正整數 \(R\)、\(C\)、\(K\)，代表盤面有 \(R\) 列、\(C\) 欄，共有 \(K\) 個單字。

接下來 \(K\) 行依處理的順序描述每個單字，每行有三個整數 \(r\)、\(c\)、\(D\) 和一個單字 \(w\)，代表從 \((r, c)\) 往方向 \(D\) 放單字 \(w\)。

同一行的資料之間以一個空白隔開。

限制

• \(1 \le R \le 200\)
• \(1 \le C \le 200\)
• \(1 \le K \le 100\)
• \(1 \le r \le R\)，\(1 \le c \le C\)
• \(D\) 是 \(0\) 或 \(1\)。
• 每個單字由 \(2\)～\(200\) 個大寫英文字母（A～Z）組成。

輸出格式

輸出 \(R\) 行，第 \(r\) 行有 \(C\) 個字元，依序是第 \(r\) 列第 \(1\)～\(C\) 欄的格子顯示的字元（*、_ 或大寫英文字母），字元之間不加空白。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

1 15 2
1 1 0 PYTHON
1 9 0 JAVA

範例輸出 1

P____N**J__A***

範例解釋 1

PYTHON 從 \((1, 1)\) 放到 \((1, 6)\)：第一個字母 P 和最後一個字母 N 顯示字母，中間的 Y、T、H、O 顯示 _。JAVA 從 \((1, 9)\) 放到 \((1, 12)\)，顯示 J__A。第 \(7\)、\(8\) 欄和第 \(13\)～\(15\) 欄沒有單字經過，顯示 *。

範例輸入 2

5 5 5
1 3 1 HELLO
1 3 0 HOLO
3 1 0 SALES
5 3 0 OAK
2 2 1 TEA

範例輸出 2

**H**
**_**
S___S
**_**
**O_K

範例解釋 2

依序處理五個單字：

1. HELLO 從 \((1, 3)\) 往下放到 \((5, 3)\)，放上。
2. HOLO 從 \((1, 3)\) 往右放，要用到 \((1, 3)\)～\((1, 6)\)，但盤面只有 \(5\) 欄，最後一個字母 O 超出盤面，所以整個不放。雖然第一個字母 H 和 \((1, 3)\) 原本的 H 相同，\((1, 4)\)、\((1, 5)\) 也是空的，還是一個字母都不放。
3. SALES 從 \((3, 1)\) 往右放到 \((3, 5)\)。\((3, 3)\) 已經有 HELLO 的 L，SALES 在這一格也是 L，共用這一格，放上。
4. OAK 從 \((5, 3)\) 往右放到 \((5, 5)\)。\((5, 3)\) 已經有 HELLO 的 O，相同，放上。
5. TEA 從 \((2, 2)\) 往下放，要用到 \((2, 2)\)、\((3, 2)\)、\((4, 2)\)。\((3, 2)\) 已經有 SALES 的 A（輸出時顯示成 _），TEA 在這一格卻是 E，不同，所以整個不放，\((2, 2)\)、\((4, 2)\) 也維持空的。

下圖是處理完之後格子裡實際的字母。綠底的格子是某個單字的第一個或最後一個字母，輸出時顯示字母；灰色字母的格子只當過中間的字母，輸出時顯示 _。紅色虛線框是沒有放上去的 HOLO 和 TEA，第 \(6\) 欄在盤面外，\((3, 2)\) 是 TEA 衝突的格子。

\((5, 3)\) 是 HELLO 的最後一個字母，也是 OAK 的第一個字母，顯示 O；\((3, 3)\) 在 HELLO 和 SALES 裡都是中間的字母，顯示 _。

題目來源

APCS 2026 年 10 月中級實作題第 2 題。

官方未公布題本，題敘依考生考後回憶整理，細節可能與正式試題有出入。