https://zerojudge.tw/ShowProblem?problemid=m372
題意#
一個 \(n \times m\) 的表格上每格有一個水管
水管分成 \(H、I、F、7、L\) 等類型
每種水管可能連接到上、下、左、右其中某些方向
求將水管連起來後最大連通塊
*本題詳細題意建議直接進 ZeroJudge 題目頁面查看
想法#
簡單來說只要對整張圖做 DFS 並一邊維護連通塊大小即可
比較麻煩的地方就是建圖而已
時間複雜度 \(O(nm)\)
考點#
- 主要考點
- DFS
- BFS
程式碼#
#include <bits/stdc++.h>
using namespace std;
// 上 右 下 左
map<char, vector<int>> 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}},
};
vector<int> graph[500000]; // 存圖
bool vis[500000]; // 紀錄造訪過的點
int ans = 0, cur = 0;
int n, m;
// 對每座標分配一個 id
int id (int x, int y) {
return x * m + y;
}
// DFS 並維護連通塊大小
void dfs(int id) {
cur++;
vis[id] = true;
for (auto &u : graph[id]) {
if (vis[u]) continue;
vis[u] = true;
dfs(u);
}
}
signed main() {
cin >> n >> m;
vector<string> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
// 建立整張圖
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 上配下
if (i + 1 < n && mask[v[i][j]][2] && mask[v[i + 1][j]][0]) {
graph[id(i, j)].push_back(id(i + 1, j));
graph[id(i + 1, j)].push_back(id(i, j));
}
// 左配右
if (j + 1 < m && mask[v[i][j]][1] && mask[v[i][j + 1]][3]) {
graph[id(i, j)].push_back(id(i, j + 1));
graph[id(i, j + 1)].push_back(id(i, j));
}
}
}
// 對每一個節點做 DFS
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cur = 0;
dfs(id(i, j));
ans = max(ans, cur); // 嘗試更新答案
}
}
cout << ans << endl;
}
