尋寶遊戲 題解|APCS 2026 年 10 月中級 第 1 題


簡潔題意

\(R\) 列 \(C\) 欄的藏寶地圖,\((r, c)\) 是第 \(r\) 列第 \(c\) 欄(都從 \(1\) 開始),每一格的寶藏價值 \(y\) 是 \(0\)~\(10^4\) 的整數。共探勘 \(K\) 次:每次以 \((r, c)\) 為中心,往上、往下各延伸 \(s\) 列,往左、往右各延伸 \(t\) 欄,輸入用 \(2s + 1\) 行、每行 \(2t + 1\) 個數,由上而下、由左而右給出這個長方形裡每一格的探勘值 \(x\),超出地圖的格子是 \(-1\)。地圖內的格子,這次探勘的中心 \(x = 2y\)、其他格子 \(x = y\);格子在整張地圖的第 \(1\) 列或第 \(R\) 列時,改成中心 \(x = 2(y + 1)\)、其他格子 \(x = y + 1\)(\(R = 1\) 時也只加一次 \(1\))。是不是中心只看那一次探勘;同一格被探勘好幾次時,算出的 \(y\) 都一樣。輸出每一格的 \(y\),沒被探勘到的格子輸出 \(-1\)(\(1 \le R, C \le 100\),\(1 \le K \le 50\),\(0 \le s, t \le 10\))。

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

  • 子題組 1(\(60\) 分):\(R = 1\),且每次探勘 \(s = 0\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):地圖只有一列,每一格都要減 1

\(R = 1\) 時地圖只有一列;每次探勘 \(s = 0\),只有一行 \(2t + 1\) 個數,由左而右依序是第 \(c - t\) 欄到第 \(c + t\) 欄。所以讓 j 從 c - t 跑到 c + t,每一圈讀一個數,讀到的就是第 j 欄的探勘值。

  • j 小於 \(1\) 或大於 \(C\) 的格子在地圖外(探勘值是 \(-1\)):一樣要讀進來,再跳過。
  • 這一列同時是第 \(1\) 列和第 \(R\) 列,每一格都要減一次 \(1\):中心 \(x = 2(y + 1)\),所以 \(y = x / 2 - 1\);其他格子 \(x = y + 1\),所以 \(y = x - 1\)。
  • 答案存在陣列 y,欄號從 \(1\) 用起、多開一格(語法書 6.3)。全域陣列一開始全是 \(0\)(語法書 6.5),可是寶藏價值也可能是 \(0\),所以先跑一次迴圈把每一格設成 \(-1\),最後還是 \(-1\) 的就是沒被探勘到。
  • 同一格被探勘好幾次,題目保證每次算出來都一樣,直接蓋掉就好。
#include <bits/stdc++.h>
using namespace std;

const int MAX_C = 100;

int y[MAX_C + 1];                              // y[j]:第 j 欄的寶藏價值,從 1 用起

int main() {
    int R, C, K;
    cin >> R >> C >> K;                        // 子題組 1 保證 R = 1:地圖只有一列
    for (int j = 1; j <= C; j++) y[j] = -1;    // -1:還沒被探勘到
    for (int k = 0; k < K; k++) {
        int r, c, s, t;
        cin >> r >> c >> s >> t;               // 子題組 1 保證 s = 0:只有一行
        for (int j = c - t; j <= c + t; j++) { // 這一行依序是第 c - t 欄到第 c + t 欄
            int x;
            cin >> x;
            if (j < 1 || j > C) continue;      // 地圖外,探勘值是 -1
            if (j == c) y[j] = x / 2 - 1;      // 中心:x = 2(y + 1)
            else y[j] = x - 1;                 // 其他格子:x = y + 1
        }
    }
    for (int j = 1; j <= C; j++) {
        if (j > 1) cout << ' ';
        cout << y[j];
    }
    cout << '\n';
    return 0;
}

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

從 60 分到 100 分:中心只看這一次,減 1 看整張地圖

一次探勘有 \(2s + 1\) 行、每行 \(2t + 1\) 個數:第 \(a\) 行第 \(b\) 個數(都從 \(0\) 數)是地圖的 \((r - s + a, c - t + b)\)。讓 i 從 r - s 跑到 r + s、裡面的 j 從 c - t 跑到 c + t,每一圈讀一個數,讀到的就是 \((i, j)\) 的探勘值——cin 不管換行,照順序一個一個讀就對了。答案改存二維陣列 y[i][j],列、欄都從 \(1\) 用起(語法書 6.9)。

圖 1 是自測表第 1 列的那一次探勘:地圖 \(3\) 列 \(3\) 欄,中心 \((3, 1)\)、\(s = t = 1\)。三行依序是第 \(2\)、\(3\)、\(4\) 列,每行的三個數依序是第 \(0\)、\(1\)、\(2\) 欄;第 \(4\) 列和第 \(0\) 欄在地圖外,探勘值都是 \(-1\)。

圖 1:3 列 3 欄的地圖,這次探勘的中心是 (3, 1)、s = t = 1,綠框是探勘範圍:第 2~4 列、第 0~2 欄。輸入的第 0 行 -1 0 6 放在第 2 列,第 1 行 -1 10 8 放在第 3 列,第 2 行 -1 -1 -1 放在第 4 列;第 4 列和第 0 欄在地圖外(虛線格),探勘值都是 -1。中心 (3, 1) 的 10 是實心底。整張地圖的第 1 列和第 3 列(第 R 列)塗成淺橘色、標著要減 1;第 2 列是探勘範圍的最上面一列,沒有塗色、標著不用減

i、j 不在地圖裡的格子要跳過,不能寫進陣列:i、j 最小可能是 \(1 - 10 = -9\)、最大可能是 \(100 + 10 = 110\),寫進去會超出陣列的範圍(語法書 6.8)。

地圖內的格子,反推 \(y\) 要問兩個問題:

  1. 是不是這一次探勘的中心(i == r && j == c):是就先除以 \(2\),\(2(y + 1)\) 變成 \(y + 1\)、\(2y\) 變成 \(y\)。
  2. 在不在整張地圖的第 \(1\) 列或第 \(R\) 列(i == 1 || i == R):在就再減 \(1\)。看的是 \(1\) 和 \(R\),不是這次探勘範圍的最上、最下列 r - s、r + s。

兩個問題各管各的、可以同時成立(中心在第 \(1\) 列或第 \(R\) 列時,要除、也要減),所以寫成兩個 if,不是 if / else if(語法書 3.11)。第二個問題是一個條件,\(R = 1\) 時 i == 1、i == R 都成立,也只減一次。

照圖 1 走一次:\((3, 1)\) 是中心、又在第 \(R\) 列,\(10 / 2 - 1 = 4\);\((3, 2)\) 在第 \(R\) 列、不是中心,\(8 - 1 = 7\)。第 \(2\) 列是這次探勘的最上面一列,但它是地圖中間的列,\((2, 1)\)、\((2, 2)\) 的探勘值 \(0\)、\(6\) 就是寶藏價值。

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

const int MAX_R = 100;
const int MAX_C = 100;

int y[MAX_R + 1][MAX_C + 1];       // y[i][j]:第 i 列第 j 欄的寶藏價值,列、欄都從 1 用起

int main() {
    int R, C, K;
    cin >> R >> C >> K;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            y[i][j] = -1;              // -1:還沒被探勘到
    for (int k = 0; k < K; k++) {
        int r, c, s, t;
        cin >> r >> c >> s >> t;
        for (int i = r - s; i <= r + s; i++) {         // 2s + 1 行依序是第 r - s 列到第 r + s 列
            for (int j = c - t; j <= c + t; j++) {     // 每一行依序是第 c - t 欄到第 c + t 欄
                int x;
                cin >> x;
                if (i < 1 || i > R || j < 1 || j > C) continue;   // 地圖外,探勘值是 -1
                int v = x;
                if (i == r && j == c) v = x / 2;       // 這一次探勘的中心:除以 2
                if (i == 1 || i == R) v -= 1;          // 整張地圖的第 1 列或第 R 列:再減 1
                y[i][j] = v;
            }
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (j > 1) cout << ' ';
            cout << y[i][j];
        }
        cout << '\n';
    }
    return 0;
}

探勘值最多 \(50 \times 21 \times 21 = 22050\) 個,一下就讀完。\(R = 1\)、\(s = 0\) 時這份程式和子題組版算的一樣,子題組 1 也對。

測過再交:範例 2 沒探勘到第 R 列

範例考到了第 \(1\) 列的中心、往上伸出地圖、同一格這次是中心下次不是(兩種順序都有)。但範例 2 的第 \(R\) 列一格都沒探勘到,只減第 \(1\) 列也會過;探勘也沒有往下、往左、往右伸出地圖,中間的列沒有寶藏價值 \(0\) 的格子,也沒有 \(R = 1\) 而 \(s > 0\) 的探勘。自己補上:

輸入 正確輸出 這一筆在測什麼
3 3 / 1 / 3 1 1 1 / -1 0 6 / -1 10 8 / -1 -1 -1 -1 -1 -1 / 0 6 -1 / 4 7 -1 圖 1:第 \(R\) 列的中心、其他格子都要減 \(1\);第 \(2\) 列是探勘範圍的最上面一列,卻不用減;\((2, 1)\) 在中間的列、探勘值是 \(0\);往左、往下伸出地圖
1 1 / 1 / 1 1 1 1 / -1 -1 -1 / -1 20002 -1 / -1 -1 -1 10000 \(R = 1\) 而 \(s = 1\)(只有子題組 2 有):一次探勘有三行,上下兩行在地圖外;寶藏價值最大的中心
1 2 / 2 / 1 1 0 2 / -1 -1 2 10001 -1 / 1 2 0 0 / 20002 0 10000 子題組 1:往左、往右伸出地圖;\((1, 1)\) 是中心、寶藏價值 \(0\);\((1, 2)\) 先當其他格子、再當中心

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

常犯錯誤
  • 「第 \(1\) 列或第 \(R\) 列」看成探勘範圍的最上、最下列(i == r - s || i == r + s):範例 2 第 2 行印 0 7 12。
  • 只寫 i == 1,漏了第 \(R\) 列:子題組 1 全對、兩個範例也都過(範例 2 沒探勘到第 \(4\) 列),自測表第 1 列第 3 行印 5 8 -1。
  • 分開寫 if (i == 1) v -= 1; 和 if (i == R) v -= 1;:\(R = 1\) 時減兩次,範例 1 印 -1 -1 0 -1。
  • 兩個問題寫成 if / else if:在第 \(1\) 列的中心只做了一步,範例 1 印 -1 0 2 0(先問第 2 個問題的話印 -1 0 3 0)。
  • 迴圈只跑地圖裡的欄(j 從 max(1, c - t) 跑到 min(C, c + t)):地圖外的 \(-1\) 沒讀掉,後面的數全部錯位——兩個範例都過(探勘沒有往左右伸出地圖),自測表第 3 列印 -1 -2。
  • 留著子題組版當 \(R = 1\) 的分支:\(R = 1\) 但 \(s > 0\) 的探勘只讀了一行——兩個範例都過,自測表第 2 列印 -1。
  • 以為 = {-1} 會把陣列都設成 \(-1\):只有第一格是 \(-1\)、其他是 \(0\)(語法書 6.9),沒被探勘到的格子印 \(0\),範例 1 印 0 0 1 0。
  • 用探勘值判斷地圖外,寫成 x <= 0:中間的列寶藏價值 \(0\) 的格子探勘值也是 \(0\),被跳過——兩個範例都過,自測表第 1 列第 2 行印 -1 6 -1。