搬家 (APCS 2023-10 中高級)

1.0s 256M

搬家

忍者龜住在下水道中，他們正在準備搬家。下水道可以用一個 \(n\times m\) 的矩陣表示，每一格的字元代表該格水管的開口方向。

若兩個上下或左右相鄰的水管，在彼此相對的方向都具有開口，便可以互相連接。能夠經由一連串相連水管互相到達的水管，屬於同一個連通塊。請找出最大的連通塊包含幾個水管。

各字元所代表的開口方向如下：

字元 開口方向
F 右、下
H 左、右
7 左、下
I 上、下
X 上、下、左、右
L 右、上
J 左、上
0 沒有水管

水管形狀

輸入格式

第一行包含兩個以空格分隔的整數 \(n\) 與 \(m\)，分別代表矩陣的列數與行數。

接下來 \(n\) 行，每行包含一個長度為 \(m\) 的字串，描述下水道中的水管配置。每個字元皆為 F、H、7、I、X、L、J 或 0。

輸出格式

輸出一個整數，代表最大連通塊中的水管數量。若矩陣中沒有水管，輸出 \(0\)。

資料範圍

  • \(1\le n,m\le 500\)
  • 每筆測試資料的執行時間限制皆為 1 秒。
  • 本題共有 20 筆計分測試資料，每筆 5 分；依正確通過的測試資料筆數給分。

子題

子題 分數 額外限制
1 60 下水道中不會出現 X
2 40 無額外限制

範例輸入 1

3 4
FHH7
IIII
LHHJ

範例輸出 1

10

範例輸入 2

4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ

範例輸出 2

9

範例說明

範例 1：

範例 1 的水管連通情形

範例 2：

範例 2 的水管連通情形

題目來源

APCS 2023 年 10 月程式實作題第 3 題「搬家」，亦收錄於 ZeroJudge m372。

題目頁說明

快速鍵

主要功能

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

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB （約 100 萬字元）
  • 自訂測試與範例測試共用一個沙箱，每人約 3 秒 1 次 （範例測試 1 秒 1 次）
  • 自訂測試與範例測試都有 15 秒 牆鐘上限（正式評測仍依題目原本時限）
  • 互動題不提供自訂測試（無法模擬與 judge 互動）。
  • 提交評測本身沒有 rate limit，但同題短時間內多次提交會被視為刷分。