# APCS實作題2023年10月第3題：搬家
> 日期：2024年8月9日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m372)
## 題目
### 問題描述
忍者龜住在下水道中，他們正在準備搬家。下水道由 $n \times m$ 的矩陣表示，其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接，它們屬於同一個連通塊。你需要找出最大的連通塊的大小。
其中，X 代表十字架，而 H、I、F、7、L 分別代表其他不同形狀的水管。0 字元代表沒有水管連接的地方。
請注意，在某個連通塊內的水管可以連接，而不同連通塊的水管不會相互連接。
下面是一些可能的水管形狀，水管的開口方向與字元對應關係。
- F：右和下
- H：左和右
- 7：左和下
- I：上和下
- X：上、下、左和右
- L：右和上
- J：左和上
- 0：沒有水管
<br />
### 輸入說明
第一行包含兩個整數：$n$ 和 $m$，以空格分隔。它們分別代表下水道矩陣的行數和列數。
接下來的 $n$ 行，每行包含 $m$ 個字元，用於表示下水道的樣子。這些字元描述了各種水管的不同形狀，以及沒有水管的地方。不同的字元代表不同的水管形狀，如 H、I、F、7、L 和 0。水管形狀的解釋在題目敘述中有詳細說明。
請注意，連接在一起的相同形狀的水管屬於同一個連通塊，但不同連通塊之間的水管是不會相互連接的。
所有測試資料皆滿足 $1 \leq n, m \leq 500$。
子題分數：
- 60%：不會有 X 出現在下水道。
- 40%：一般情況。
<br />
### 輸出格式
輸出出最大連通塊的大小。
<br />
### 範例輸入1
```
3 4
FHH7
IIII
LHHJ
```
### 範例輸出1
```
10
```
### 範例輸入2
```
4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ
```
### 範例輸出2
```
9
```
<br /><br />
## Python 程式碼
以下是解題的想法。
1. 第3 ~ 10行，用字典 op 儲存各種水管對應的開口方向，依序為右、上、左、下。
2. 第13行，儲存地圖用的二維串列維度為 $(n+1) \times (m+1)$，這是為了在最右側、最下方加上字元 0 作為哨兵，進行四方向檢查時，如果遇到字元 0 就是碰到不通的格子或邊界，可以避開索引值出界的問題。由於 Python 的串列索引值為 -1 時會讀取串列的最後一格，所以只要在最右側、最下方放置哨兵即可，如果改用 C++，則要在四周都加上哨兵。
3. 第31 ~ 41行，類似廣度優先走訪的寫法，執行完畢時，會將相連的區塊加上相同的編號。
4. 第38行，在檢查 (pr, pc) 及 (nr, nc) 的開口是否相連時，兩者的開口方向為「右對左、上對下、左對右、下對上」，換成 op 資料對應的索引值就是「0對2、1對3、2對0、3對1」，再換成變數就是「i 對 (i+2)%4」。
費時最久約為 1.8 s，使用記憶體最多約為 32.6 MB，通過測試。
```python=
#from pprint import pprint # pprint 可以用來印出二維串列
# 水管的開口方向與字元對應關係 (右, 上, 左, 下)
op = {'F': (True, False, False, True),
'H': (True, False, True, False),
'7': (False, False, True, True),
'I': (False, True, False, True),
'X': (True, True, True, True),
'L': (True, True, False, False),
'J': (False, True, True, False),
'0': (False, False, False, False)}
n, m = map(int, input().split()) # 讀取 n, m
grid = [['0']*(m+1) for _ in range(n+1)] # (m+1)*(n+1) 的二維串列，儲存地圖，右側、下方加上 '0' 作為哨兵
for i in range(n): # 讀取 n 行資料
s = input() # 讀取整行字串
for j in range(m): grid[i][j] = s[j] # 依序取出字元填入 grid
label = [[0]*m for _ in range(n)] # n*m 的二維串列，相連的區塊編號相同，0代表還沒有編號
cnt = [0] # 記錄不同編號區塊的數量，cnt[0] = 0
idx = 0 # 相連的區塊編號
""" 主要的解題過程 """
for r in range(n): # 依序産生 0 ~ n-1
for c in range(m): # 依序産生 0 ~ m-1
if grid[r][c] == '0': continue # 如果這格是 '0'，不通，檢查下一格
if label[r][c] != 0: continue # 如果這格已有標記，檢查下一格
idx += 1 # 新的相連區塊，編號加 1
label[r][c] = idx # 更新 (r, c) 的編號
cnt.append(1) # 新增一項，cnt[idx] = 1
st = [(r, c)] # 待檢查格子的串列，先放入 (r, c)
head = 0 # 由 st 讀取資料的索引值
while head < len(st): # 如果 head 還沒有出界繼續執行
pr, pc = st[head] # 由 st 讀取目前的位置 (pr, pc)
head += 1 # head 加 1
for i, (dr, dc) in enumerate(((0, 1), (-1, 0), (0, -1), (1, 0))): # 依序檢查右、上、左、下
nr = pr + dr; nc = pc + dc # 更新要檢查的格子位置 (nr, nc)
if grid[nr][nc] == '0': continue # 如果這格是 '0'，不通，檢查下一格
if label[nr][nc] != 0: continue # 如果這格已有標記，檢查下一格
if op[grid[pr][pc]][i] and op[grid[nr][nc]][(i+2)%4]: # 如果 (pr, pc) 及 (nr, nc) 能接通
label[nr][nc] = idx # 更新 (nr, nc) 的編號
cnt[idx] += 1 # idx 對應的數量加 1
st.append((nr, nc)) # 將 (nr, nc) 加入 st
#pprint(label) # 印出 label，除錯用
""" 結束解題過程 """
print(max(cnt)) # 印出答案
```
<br /><br />
## C++ 程式碼
程式運作邏輯與 Python 版本相同，但是在哨兵的部分寫法不同，因為 C++ 的陣列索引值沒有負數，要在四周都加上哨兵，因此 grid 的維度為 $(n+2) \times (m+2)$，填入資料時索引值為 1 ~ n 及 1 ~ m。
費時最久約為 39 ms，使用記憶體最多約為 20.8 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
// 水管的開口方向與字元對應關係 (右, 上, 左, 下)
map<char, vector<bool>> op = {{'F', {true, false, false, true}},
{'H', {true, false, true, false}},
{'7', {false, false, true, true}},
{'I', {false, true, false, true}},
{'X', {true, true, true, true}},
{'L', {true, true, false, false}},
{'J', {false, true, true, false}},
{'0', {false, false, false, false}}};
int n, m; cin >> n >> m; // 讀取 n, m
vector<vector<char>> grid (n+2, vector<char> (m+2, '0')); // (m+2)*(n+2) 的二維陣列，儲存地圖，四周加上 '0' 作為哨兵
for(int i=1; i<=n; i++) { // 讀取 n 行資料
string s; cin >> s; // 讀取整行字串
for(int j=1; j<=m; j++) grid[i][j] = s[j-1]; // 依序取出字元填入 grid，s 的長度是 m，讀取時索引值為 j-1
}
vector<vector<int>> label (n+1, vector<int> (m+1, 0)); // (n+1)*(m+1) 的二維陣列，相連的區塊編號相同，0代表還沒有編號
vector<int> cnt = {0}; // 記錄不同編號區塊的數量，cnt[0] = 0
int idx = 0; // 相連的區塊編號
int dirs[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; // 四方向檢查用的 (dr, dc)
/* 主要的解題過程 */
for(int r=1; r<=n; r++) { // 依序産生 1 ~ n
for(int c=1; c<=m; c++) { // 依序産生 1 ~ m
if (grid[r][c] == '0') continue; // 如果這格是 '0'，不通，檢查下一格
if (label[r][c] != 0) continue; // 如果這格已有標記，檢查下一格
idx++; // 新的相連區塊，編號加 1
label[r][c] = idx; // 更新 (r, c) 的編號
cnt.push_back(1); // 新增一項，cnt[idx] = 1
vector<vector<int>> st = {{r, c}}; // 待檢查格子的串列，先放入 (r, c)
size_t head = 0; // 由 st 讀取資料的索引值
while(head < st.size()) { // 如果 head 還沒有出界繼續執行
int pr = st[head][0], pc = st[head][1]; // 由 st 讀取目前的位置 (pr, pc)
head++; // head 加 1
for(int i=0; i<4; i++) { // 依序檢查右、上、左、下
int nr = pr + dirs[i][0], nc = pc + dirs[i][1]; // 更新要檢查的格子位置 (nr, nc)
if (grid[nr][nc] == '0') continue; // 如果這格是 '0'，不通，檢查下一格
if (label[nr][nc] != 0) continue; // 如果這格已有標記，檢查下一格
if (op[grid[pr][pc]][i] && op[grid[nr][nc]][(i+2)%4]) { // 如果 (pr, pc) 及 (nr, nc) 能接通
label[nr][nc] = idx; // 更新 (nr, nc) 的編號
cnt[idx]++; // idx 對應的數量加 1
st.push_back({nr, nc}); // 將 (nr, nc) 加入 st
}
}
}
}
}
/* 結束解題過程 */
cout << *max_element(cnt.begin(), cnt.end()) << "\n"; // 印出答案
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet