花圃區域選擇 (APCS 2026-06 中級)
2.0s 256M學校有一塊花圃,劃成 \(N\) 列、\(M\) 欄的方格。列由上而下編號為 \(0 \sim N - 1\),欄由左而右編號為 \(0 \sim M - 1\),第 \(i\) 列第 \(j\) 欄的格子記為 \((i, j)\),所以左上角是 \((0, 0)\)。每一格有一個整數 \(A_{i,j}\):
- \(A_{i,j} = -1\):這一格有障礙物,不能種花;
- \(A_{i,j}\) 是正整數:這一格種的是第 \(A_{i,j}\) 種花。
校長要在花圃裡圈出一塊 \(R\) 列、\(C\) 欄的長方形區域。區域的位置用它的左上角 \((i, j)\) 表示:它包含第 \(i \sim i + R - 1\) 列、第 \(j \sim j + C - 1\) 欄的每一格,而且整塊都要在花圃裡面。
校長挑選區域的規則依序是:
- 區域裡不能有任何障礙物。
- 符合第 1 條的區域中,花的種類數越多越好。同一種花不論在區域裡出現幾格,都只算一種。
- 種類數一樣多時,選左上角 \(i + j\) 最小的。
- \(i + j\) 也一樣時,選左上角 \(i\) 最小的。
請輸出校長選中的區域的左上角 \((i, j)\),以及這塊區域裡花的種類數。題目保證至少有一塊區域裡沒有障礙物。
輸入格式
第一行有四個正整數 \(N\)、\(M\)、\(R\)、\(C\)。
接下來有 \(N\) 行,依序是第 \(0 \sim N - 1\) 列;每行有 \(M\) 個整數,依序是這一列第 \(0 \sim M - 1\) 欄的 \(A_{i,j}\)。
同一行的整數之間以一個空白隔開。
限制
- \(1 \le R \le N \le 50\)
- \(1 \le C \le M \le 50\)
- \(A_{i,j} = -1\) 或 \(1 \le A_{i,j} \le N \times M\)
- 至少有一塊 \(R \times C\) 的區域裡沒有障礙物。
輸出格式
輸出一行,包含三個整數 \(i\)、\(j\)、\(k\),以一個空白隔開:校長選中的區域左上角是 \((i, j)\),區域裡有 \(k\) 種花。
評分說明
每一筆測試資料的執行時間限制均為 \(2\) 秒,依正確通過的測試資料筆數給分。
| 子題組 | 分數 | 額外限制 |
|---|---|---|
| 1 | 20 | \(R = 1\),\(C = 1\) |
| 2 | 30 | 花圃裡沒有障礙物(每一個 \(A_{i,j}\) 都不是 \(-1\)) |
| 3 | 50 | 無額外限制 |
範例輸入 1
3 4 2 2
1 2 3 4
2 3 -1 5
1 2 4 5
範例輸出 1
0 0 3
範例解釋 1
花圃有 \(3\) 列 \(4\) 欄,要圈 \(2 \times 2\) 的區域,左上角可以是 \(i = 0, 1\)、\(j = 0, 1, 2\),共 \(6\) 個位置。下圖深色的格子是障礙物,粗框是校長選中的區域。
| 左上角 | 有障礙物 | 種類數 | \(i + j\) |
|---|---|---|---|
| \((0, 0)\) | 沒有 | 3 | 0 |
| \((0, 1)\) | 有 | — | — |
| \((0, 2)\) | 有 | — | — |
| \((1, 0)\) | 沒有 | 3 | 1 |
| \((1, 1)\) | 有 | — | — |
| \((1, 2)\) | 有 | — | — |
沒有障礙物的區域只有左上角 \((0, 0)\) 和 \((1, 0)\) 兩塊。\((0, 0)\) 那塊的花是 \(1, 2, 2, 3\),第 \(2\) 種花出現兩格只算一種,共 \(3\) 種;\((1, 0)\) 那塊也是 \(3\) 種。種類數一樣多,選 \(i + j\) 比較小的 \((0, 0)\)。
範例輸入 2
4 5 2 3
1 2 3 4 5
2 3 4 5 6
-1 1 2 3 4
7 8 9 1 2
範例輸出 2
1 1 5
範例解釋 2
要圈 \(2 \times 3\) 的區域,左上角可以是 \(i = 0, 1, 2\)、\(j = 0, 1, 2\),共 \(9\) 個位置。
| 左上角 | 有障礙物 | 種類數 | \(i + j\) |
|---|---|---|---|
| \((0, 0)\) | 沒有 | 4 | 0 |
| \((0, 1)\) | 沒有 | 4 | 1 |
| \((0, 2)\) | 沒有 | 4 | 2 |
| \((1, 0)\) | 有 | — | — |
| \((1, 1)\) | 沒有 | 5 | 2 |
| \((1, 2)\) | 沒有 | 5 | 3 |
| \((2, 0)\) | 有 | — | — |
| \((2, 1)\) | 沒有 | 5 | 3 |
| \((2, 2)\) | 沒有 | 5 | 4 |
最多有 \(5\) 種花,左上角 \((1, 1)\)、\((1, 2)\)、\((2, 1)\)、\((2, 2)\) 這四塊都是,其中 \(i + j\) 最小的是 \((1, 1)\)。
如果 \((1, 1)\) 那塊不能選,剩下的 \((1, 2)\) 和 \((2, 1)\) 的 \(i + j\) 都是 \(3\),就要選 \(i\) 比較小的 \((1, 2)\)。
題目來源
APCS 2026 年 6 月中級實作題第 2 題。
官方未公布題本,題敘參考 APCS Simulation 整理,細節可能與正式試題有出入。