m372. 3. 搬家
Tags :
Accepted rate : 290人/375人 ( 77% ) [非即時]
評分方式:
Tolerant

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

Content

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

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

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

 

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


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

Input

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

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

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

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

子題分數:

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

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

Sample Input #1
3 4
FHH7
IIII
LHHJ
Sample Output #1
10
Sample Input #2
4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ
Sample Output #2
9
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

範例輸入 1 示意圖

範例輸入 2 示意圖

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

Status Forum 排行

ID User Problem Subject Hit Post Date
38134 xx0932399@gm ... (Dada878) m372
883 2023-10-29 16:15
38100 jamil130011@ ... (許恩嘉) m372
1208 2023-10-25 21:31
39467 jamil130011@ ... (許恩嘉) m372
C++遞迴解法
169 2024-02-24 22:21
38597 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) m372
注意!
268 2023-12-09 16:23
38469 alec5106@gma ... (Alec Chen) m372
用遞迴
275 2023-11-27 08:58