花圃區域選擇 題解|APCS 2026 年 6 月中級 第 2 題


簡潔題意

\(N \times M\) 的花圃(\(N, M \le 50\)),第 \(i\) 列第 \(j\) 欄記為 \((i, j)\),列、欄都從 \(0\) 開始編號;每格是 \(-1\)(障礙物)或花的種類編號(\(1\) 到 \(N \times M\))。要圈一塊 \(R \times C\) 的區域,用左上角 \((i, j)\) 表示,整塊要在花圃裡。區域裡不能有障礙物;花的種類越多越好;種類一樣多選 \(i + j\) 最小的,再一樣選 \(i\) 最小的。輸出左上角的 \(i\)、\(j\) 和種類數。保證至少有一塊區域沒有障礙物。

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

  • 子題組 1(\(20\) 分):\(R = 1\),\(C = 1\)。
  • 子題組 2(\(30\) 分):沒有障礙物。
  • 子題組 3(\(50\) 分):無額外限制。

先拿下子題組 1(20 分):區域只有一格

不是 \(-1\) 的格子都只有 \(1\) 種花,種類數全部一樣,答案只看規則 3、4:在不是 \(-1\) 的格子裡找 \(i + j\) 最小的,一樣再找 \(i\) 最小的。

由上而下、由左而右掃(邊讀邊比,不用存地圖),只在 \(i + j\) 嚴格變小時才換:\(i + j\) 一樣的格子,先掃到的 \(i\) 一定比較小,換不掉它,剛好就是規則 4。直接留下第一個掃到的格子是錯的,它的 \(i + j\) 不一定最小。

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

int main() {
    int N, M, R, C;
    cin >> N >> M >> R >> C;  // 子題組 1:R = C = 1,區域就是一格
    int bestI = -1, bestJ = -1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int flower;
            cin >> flower;
            if (flower == -1) continue;  // 障礙物不能選
            // 由上而下掃:i + j 一樣的格子,先掃到的 i 比較小,所以 i + j 嚴格變小才換
            if (bestI == -1 || i + j < bestI + bestJ) {
                bestI = i;
                bestJ = j;
            }
        }
    }
    cout << bestI << ' ' << bestJ << ' ' << 1 << '\n';  // 一格只有一種花
    return 0;
}

兩個範例的區域都不只一格,這個版本對範例會 WA 是正常的;它對子題組 1 的 \(4\) 筆全對,穩拿 \(20\) 分。

從 20 分到 100 分:每個左上角都試一次

這就是「枚舉左上角」:

  1. 左上角的 \(i\) 從 \(0\) 試到 \(N - R\)、\(j\) 從 \(0\) 試到 \(M - C\),兩端都要試。迴圈寫成 i + R <= N、j + C <= M,區域就不會伸出花圃。
  2. 把區域裡的 \(R \times C\) 格都看一遍:看到 \(-1\) 就記下「這塊不能選」;不是 \(-1\) 就數種類。
  3. 數種類用 6.7 的「用陣列記錄」:seen[v] 記第 \(v\) 種花在這塊區域出現過沒有,第一次出現才加一。花的編號最大是 \(N \times M \le 2500\),陣列開 \(2505\) 格;每換一塊區域都要重新清空,所以宣告在迴圈裡面,寫成 = {} 全部歸零(6.5)。
  4. 能選的區域照規則 2、3、4 和目前最好的比,比較好才換。

子題組 2 沒有障礙物,第 2 步不會碰到 \(-1\),同一支程式照樣對。

運算量:最費時的是 \(R = C = 25\),左上角 \(26 \times 26\) 個、每塊看 \(625\) 格,約 \(4.2 \times 10^5\) 格。每塊還要清一次 seen,最多 \(2500\) 塊、每塊 \(2505\) 格,也只有幾百萬次。

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

const int MAX_N = 55;       // N、M 都不超過 50
const int MAX_KIND = 2505;  // 花的編號最大是 N × M ≤ 2500
int A[MAX_N][MAX_N];

int main() {
    int N, M, R, C;
    cin >> N >> M >> R >> C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }

    int bestI = -1, bestJ = -1, bestKinds = -1;  // bestKinds = -1:還沒找到能選的區域
    for (int i = 0; i + R <= N; i++) {  // 左上角 (i, j):整塊都要在花圃裡
        for (int j = 0; j + C <= M; j++) {
            bool blocked = false;  // 區域裡有沒有障礙物
            int kinds = 0;  // 區域裡有幾種花
            bool seen[MAX_KIND] = {};  // seen[v]:第 v 種花在這塊區域出現過了嗎(每塊重新歸零)
            for (int x = i; x < i + R; x++) {
                for (int y = j; y < j + C; y++) {
                    int flower = A[x][y];
                    if (flower == -1) {
                        blocked = true;
                    } else if (!seen[flower]) {  // 第一次看到這種花才算
                        seen[flower] = true;
                        kinds++;
                    }
                }
            }
            if (blocked) continue;  // 有障礙物:整塊不能選

            bool better;
            if (bestKinds == -1) {
                better = true;  // 第一塊能選的區域
            } else if (kinds != bestKinds) {
                better = kinds > bestKinds;  // 規則 2:種類多的優先
            } else if (i + j != bestI + bestJ) {
                better = i + j < bestI + bestJ;  // 規則 3:i + j 小的優先
            } else {
                better = i < bestI;  // 規則 4:i 小的優先
            }
            if (better) {
                bestI = i;
                bestJ = j;
                bestKinds = kinds;
            }
        }
    }
    cout << bestI << ' ' << bestJ << ' ' << bestKinds << '\n';
    return 0;
}

由上而下、由左而右掃,\(i + j\) 一樣時一定先掃到 \(i\) 小的,所以規則 4 那一行其實不會成立;三條都寫出來,就不用去想掃描順序對不對。

測過再交:範例的答案都不靠規則 4

兩個範例的答案都不是靠「\(i + j\) 一樣選 \(i\) 小的」決定的,也都沒有碰到最下面一列或最右邊一欄。下面五種錯法範例都會過(見常犯錯誤),自己補這幾筆:

輸入 正確輸出 這一筆在測什麼
2 3 1 1/-1 -1 1/1 -1 -1 1 0 1 子題組 1:最先掃到的 \((0, 2)\),\(i + j\) 是 \(2\);\((1, 0)\) 只有 \(1\)
2 2 1 1/-1 1/1 -1 0 1 1 \((0, 1)\) 和 \((1, 0)\) 的 \(i + j\) 都是 \(1\),選 \(i\) 小的
3 1 2 1/-1/1/1 1 0 1 左上角 \((0, 0)\) 那塊的第一格就是障礙物,整塊不能選;答案碰到最下面一列
1 1 1 1/1 0 0 1 整個花圃剛好是一塊區域

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

常犯錯誤
  • 只比種類數,同分留下最先掃到的:範例全過,自測表第 1 列印 0 2 1;本站 \(20\) 筆掛 \(12\) 筆。
  • 寫成 i + j <= bestI + bestJ 就換:\(i + j\) 一樣時換成後掃到的,也就是 \(i\) 比較大的。範例全過,自測表第 2 列印 1 0 1;本站 \(20\) 筆掛 \(13\) 筆。
  • 沒跳過有障礙物的區域,只是不數 \(-1\):範例全過,自測表第 3 列印 0 0 1;本站 \(20\) 筆掛 \(10\) 筆。
  • 碰到 \(-1\) 就 break,以為整塊跳過了:break 只跳出內層迴圈,下一列照樣數,這塊最後還是被當成能選。範例全過,自測表第 3 列一樣印 0 0 1;本站 \(20\) 筆掛 \(10\) 筆。
  • 左上角少試最後一列或最後一欄(i + R < N、j + C < M):範例全過,自測表第 4 列印 -1 -1 -1;少一列、少一欄各掛 \(7\) 筆。