a307. 202310_3. 搬家

Content

忍者龜住在下水道中，他們正在準備搬家。下水道由 $n \times 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≤n,m≤500$

子題分數：

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

Output

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

Sample Input #1

3 4
FHH7
IIII
LHHJ

Sample Output #1

Sample Input #2

4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ

Sample Output #2

測資資訊：

記憶體限制： 512 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 演算法海牛 [管理者： zero(管理員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」