尋寶遊戲 (APCS 2026-10 中級)

小華在玩尋寶遊戲。藏寶地圖是一個 \(R\) 列、\(C\) 欄的方格，由上而下第 \(r\) 列、由左而右第 \(c\) 欄的格子記為 \((r, c)\)，列、欄都從 \(1\) 開始編號。每一格都藏有寶藏，寶藏價值 \(y\) 是 \(0\)～\(10^4\) 的整數，但小華一開始不知道任何一格的 \(y\)。

小華可以探勘。每次探勘選一個中心格子 \((r, c)\) 和兩個整數 \(s\)、\(t\)，從中心往上、往下各延伸 \(s\) 列，往左、往右各延伸 \(t\) 欄，探勘這個 \(2s + 1\) 列、\(2t + 1\) 欄的長方形。長方形裡的每一格都會回傳一個探勘值 \(x\)；長方形超出地圖的格子，探勘值是 \(-1\)。

地圖內的格子，探勘值 \(x\) 和寶藏價值 \(y\) 的關係如下表：

• 第 \(1\) 列、第 \(R\) 列指的是整張地圖最上面和最下面的一列，不是探勘範圍的最上、最下列。
• \(R = 1\) 時，地圖只有一列，它同時是第 \(1\) 列和第 \(R\) 列，探勘值仍然照上表「在第 \(1\) 列或第 \(R\) 列」那一欄計算，只加一次 \(1\)。
• 是不是中心格子只看這一次探勘：同一格可能在某一次探勘是中心，在另一次探勘不是。

小華一共探勘了 \(K\) 次。請根據這 \(K\) 次的探勘值，算出每一格的寶藏價值；從沒被探勘到的格子無法得知寶藏價值，輸出 \(-1\)。

輸入格式

第一行有兩個整數 \(R\) 和 \(C\)，代表地圖有 \(R\) 列、\(C\) 欄。第二行有一個整數 \(K\)，代表探勘的次數。

接下來依序是 \(K\) 次探勘的結果。每一次先有一行四個整數 \(r\)、\(c\)、\(s\)、\(t\)，代表這次探勘的中心格子是 \((r, c)\)，往上、往下各延伸 \(s\) 列，往左、往右各延伸 \(t\) 欄；接著有 \(2s + 1\) 行，每行有 \(2t + 1\) 個整數，由上而下、由左而右依序是探勘範圍裡每一格的探勘值。

同一行的整數之間以一個空白隔開。

限制

• \(1 \le R \le 100\)
• \(1 \le C \le 100\)
• \(1 \le K \le 50\)
• \(1 \le r \le R\)，\(1 \le c \le C\)
• \(0 \le s \le 10\)，\(0 \le t \le 10\)
• 每一格的寶藏價值 \(y\) 都是整數，\(0 \le y \le 10^4\)。
• 探勘範圍超出地圖的格子，探勘值是 \(-1\)；地圖內的格子，探勘值依上表由那一格的寶藏價值算出。
• 同一格被探勘好幾次時，每一次的探勘值都由同一個寶藏價值算出，探勘結果互不矛盾。

輸出格式

輸出 \(R\) 行，第 \(r\) 行有 \(C\) 個整數，依序是第 \(r\) 列第 \(1\)～\(C\) 欄的寶藏價值；從沒被探勘到的格子輸出 \(-1\)。同一行的整數之間以一個空白隔開。

評分說明

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

範例輸入 1

1 4
1
1 3 0 1
1 4 1

範例輸出 1

-1 0 1 0

範例解釋 1

地圖只有 \(1\) 列，這一列同時是第 \(1\) 列和第 \(R\) 列。唯一的一次探勘以 \((1, 3)\) 為中心、\(s = 0\)、\(t = 1\)，探勘範圍是 \((1, 2)\)、\((1, 3)\)、\((1, 4)\) 三格：

\((1, 2)\)、\((1, 4)\) 不是中心，\(y + 1 = 1\)，所以 \(y = 0\)；\((1, 3)\) 是中心，\(2(y + 1) = 4\)，所以 \(y = 1\)。\((1, 1)\) 沒被探勘到，輸出 \(-1\)。

範例輸入 2

4 3
2
1 2 1 1
-1 -1 -1
1 42 1
1 7 13
2 2 1 0
21
14
37

範例輸出 2

0 20 0
1 7 13
-1 37 -1
-1 -1 -1

範例解釋 2

第 1 次探勘以 \((1, 2)\) 為中心、\(s = 1\)、\(t = 1\)，範圍是 \(3\) 列 \(3\) 欄，最上面那一列在地圖外（第 \(1\) 列的上面），探勘值都是 \(-1\)。第 2 次探勘以 \((2, 2)\) 為中心、\(s = 1\)、\(t = 0\)，範圍是 \((1, 2)\)、\((2, 2)\)、\((3, 2)\) 三格。

下圖左邊是兩次探勘的範圍和探勘值：標 1 的綠框是第 1 次、標 2 的橘框是第 2 次，實心底的數字是那一次的中心格子，虛線格在地圖外。右邊是答案。

地圖有 \(4\) 列，第 \(1\) 列和第 \(4\) 列是最上、最下的列。探勘到的每一格如下表，「探勘」是第幾次探勘，「中心」是那一次是不是以這一格為中心：

\((1, 2)\) 和 \((2, 2)\) 各被探勘兩次，一次是中心、一次不是，兩次算出的寶藏價值相同。\((1, 1)\) 和 \((2, 1)\) 的探勘值都是 \(1\)，但 \((1, 1)\) 在第 \(1\) 列，寶藏價值是 \(0\)；\((2, 1)\) 在其他列，寶藏價值是 \(1\)。其餘格子沒被探勘到，輸出 \(-1\)。

題目來源

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

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