---
# System prepended metadata

title: 2/21 m372. 3. 搬家

---

m372. 3. 搬家
===
https://zerojudge.tw/ShowProblem?problemid=m372
> graph的第i個位置的幾個元素就是他連接的有幾個管子以及連接管子的位置，dfs就是往管子的某個方向一直去遞迴
```python=
mask = {
    'X': [1, 1, 1, 1],
    'I': [1, 0, 1, 0],
    'H': [0, 1, 0, 1],
    'L': [1, 1, 0, 0],
    '7': [0, 0, 1, 1],
    'F': [0, 1, 1, 0],
    'J': [1, 0, 0, 1],
    '0': [0, 0, 0, 0]
}
# DFS函數，計算連通塊大小
def dfs(node):
    global cur
    cur += 1
    vis[node] = True
    for u in graph[node]
        if not vis[u]:
            vis[u] = True
            dfs(u)
graph = [[] for _ in range(500000)] 
vis = [False] * 500000
ans = 0 
n, m = map(int, input().split())
v = [input() for _ in range(n)]
for i in range(n):
    for j in range(m):
        if i + 1 < n and mask[v[i][j]][2] and mask[v[i + 1][j]][0]:
            graph[i * m + j].append((i + 1) * m + j)#上下方向都是1相通
            graph[(i + 1) * m + j].append(i * m + j)
        if j + 1 < m and mask[v[i][j]][1] and mask[v[i][j + 1]][3]:
            graph[i * m + j].append(i * m + j + 1) #左右方向都是1相通
            graph[i * m + j + 1].append(i * m + j)
    # 對每個節點進行DFS
for i in range(n):
    for j in range(m):
        cur = 0
        dfs(i * m + j)
        ans = max(ans, cur)
print(ans)

```