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