m372. 3. 搬家
標籤 :
通過比率 : 436人/545人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-10-26 21:51

內容

忍者龜住在下水道中,他們正在準備搬家。下水道由 $n$ x $m$ 的矩陣表示,其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接,它們屬於同一個連通塊。你需要找出最大的連通塊的大小。

其中,X 代表十字架,而 H、I、F、7、L 分別代表其他不同形狀的水管。0 字元代表沒有水管連接的地方。

請注意,在某個連通塊內的水管可以連接,而不同連通塊的水管不會相互連接。

 

下面是一些可能的水管形狀:


水管的開口方向與字元對應關係
F: 右和下
H: 左和右
7: 左和下
I: 上和下
X: 上、下、左和右
L: 右和上
J: 左和上
0: 沒有水管

輸入說明

第一行包含兩個整數:$n$ 和 $m$,以空格分隔。它們分別代表下水道矩陣的行數和列數。

接下來的 $n$ 行,每行包含 $m$ 個字元,用於表示下水道的樣子。這些字元描述了各種水管的不同形狀,以及沒有水管的地方。不同的字元代表不同的水管形狀,如 H、I、F、7、L 和 0。水管形狀的解釋在題目敘述中有詳細說明。

請注意,連接在一起的相同形狀的水管屬於同一個連通塊,但不同連通塊之間的水管是不會相互連接的。

所有測試資料皆滿足 $1 \leq n, m \leq 500$

子題分數:

  • 60%:不會有 X 出現在下水道。
  • 40%:一般情況。
輸出說明

輸出出最大連通塊的大小。

範例輸入 #1
3 4
FHH7
IIII
LHHJ
範例輸出 #1
10
範例輸入 #2
4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ
範例輸出 #2
9
測資資訊:
記憶體限制: 256 MB
提示 :

範例輸入 1 示意圖

範例輸入 2 示意圖

標籤:
出處:
2023年10月APCS [管理者: algo.seacow@ ... (演算法海牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
38134 xx0932399@gm ... (Dada878) m372
1323 2023-10-29 16:15
38100 jamil130011@ ... (許恩嘉) m372
1760 2023-10-25 21:31
42571 htchu.taiwan ... (Hsueh-Ting Chu) m372
87 2024-10-03 02:22
40955 glps1004@gma ... (Ian) m372
APCS 202410全解析
230 2024-06-21 16:03
40650 john1100729@ ... (靖諺) m372
C++ 詳解
258 2024-06-03 20:36