m372. 3. 搬家 - 高中生程式解題系統

內容

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

範例輸入 #2

4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ

範例輸出 #2

測資資訊：

記憶體限制： 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

提示：

範例輸入 1 示意圖

範例輸入 2 示意圖

標籤:

出處:

2023年10月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
38134	xx0932399@gm ... (Dada878)	m372	✅ 1 ~ 4 題實做考點分析 x 解題思路 x 詳細解法	1300	2023-10-29 16:15
38100	jamil130011@ ... (許恩嘉)	m372	C++ 不使用BFS/DFS的超快(7ms)超簡單(沒用到複雜的演算法)作法	1714	2023-10-25 21:31
42571	htchu.taiwan ... (Hsueh-Ting Chu)	m372	使用Stack記錄，取代DFS	67	2024-10-03 02:22
40955	glps1004@gma ... (Ian)	m372	APCS 202410全解析	208	2024-06-21 16:03
40650	john1100729@ ... (靖諺)	m372	C++ 詳解	242	2024-06-03 20:36