花圃區域選擇 (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. 區域裡不能有任何障礙物。
  2. 符合第 1 條的區域中,花的種類數越多越好。同一種花不論在區域裡出現幾格,都只算一種。
  3. 種類數一樣多時,選左上角 \(i + j\) 最小的。
  4. \(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\) 個位置。下圖深色的格子是障礙物,粗框是校長選中的區域。

範例 1 的花圃,3 列 4 欄;(1,2) 是障礙物;粗框圈出左上角 (0,0) 的 2 x 2 區域
左上角 有障礙物 種類數 \(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\) 個位置。

範例 2 的花圃,4 列 5 欄;(2,0) 是障礙物;粗框圈出左上角 (1,1) 的 2 x 3 區域
左上角 有障礙物 種類數 \(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 整理,細節可能與正式試題有出入。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器(per 帳號 / 題目 / 語言)。
  • 提交 — 把程式碼交給 judge 評測,回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB (約 100 萬字元)
  • 自訂測試每人約 3 秒 1 次 (範例測試 1 秒 1 次)
  • 自訂測試有 15 秒 牆鐘上限;範例測試和正式評測一樣,照題目的時間限制
  • 互動題不提供自訂測試(無法模擬與 judge 互動)。
  • 提交評測本身沒有 rate limit,但同題短時間內多次提交會被視為刷分。