搬家

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;
}