# m372. 3. 搬家
### 題目網址: https://zerojudge.tw/ShowProblem?problemid=m372

---

### 解題思路
* 需要用到的函式：
1. canconnect(目前水管，目標水管，連通方向) : 用來判斷某個方向能不能接通。
2. DFS 主迴圈 : 不斷往四個方向擴張，只要「沒出界」且「水管接得通」且「沒走過」，就繼續遞迴並計數。
3. main主程式 : 掃描地圖上的每一個點 $(i, j)$如果該點 有水管 且 沒被拜訪過 $\rightarrow$ 發動一次 DFS。
每次 DFS 結束會回傳一個大小，代表跟他連結的水管數量，紀錄最大的那個就是答案。
* 需要用到的變數 :
1. grid地圖
2. visited 用來存是否走過(我喜歡叫他影子地圖
3. pipetype 定義水管開口
4. dx dy op 偏移量

---

### 程式碼 DFS版本

#include<bits/stdc++.h>
using namespace std;
//全域變數
char grid[600][600]={"0"}; //地圖
int visited[600][600]={{0}}; //是否走過 0為沒走過
int n,m;

map<char,vector<bool>> pipetype={ //定義每個水管的開口：上, 下, 左, 右
//       上     下     左     右
{'I', {true,  true,  false, false}},
{'H', {false, false, true,  true }},
{'L', {true,  false, false, true }},
{'J', {true,  false, true,  false}},
{'7', {false, true,  true,  false}},
{'F', {false, true,  false, true }},
{'X', {true,  true,  true,  true }}
};

//偏移量   上 下 左 右
int dx[4]={0,0,-1,1}; 
int dy[4]={-1,1,0,0};
int op[4]={1,0,3,2};// 這是反方向，例如我要找目前跟上方的管子k=0對到map的上，此時op[k]=1 對應到map的下

bool canconnect(char a,char b,int k){//判斷兩根水管可不可以連接
  return pipetype[a][k] && pipetype[b][op[k]];//兩個都是true才會回傳true
}
int dfs(int cury,int curx){//目前座標
  visited[cury][curx]=1;//標記成已經走過
  int count=1;//這裡算一格
  //嘗試往四周擴散
  for(int k=0;k<4;k++){
    int ny=cury+dy[k];
    int nx=curx+dx[k];
    //1.邊界檢查
    if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
    //2.接通檢查
    if(grid[ny][nx]!='0' && visited[ny][nx]==0 && canconnect(grid[cury][curx],grid[ny][nx],k)){ //不是空氣 沒有走過 可以連接
      count+=dfs(ny,nx); //繼續遞迴，並且把底下算出的值加上目前的count，就是這層的聯通管子數
    }
  }
  return count;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>grid[i][j];
    }
  }
  //count
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(grid[i][j]!='0' && visited[i][j]==0){ //不是空氣而且沒走過
        ans=max(ans,dfs(i,j));//開始dfs，並且把每次算完的值取最大的
      }
    }
  }
  cout<<ans<<endl;
}

這個程式碼最後有一個測資過不了，顯示記憶體區段錯誤，我詢問過其他高手們，他們推測可能是遞迴太深導致stack爆掉，他們還推薦我試試其他方式。
* DFS用的是 「系統堆疊 (System Stack)」，這個空間很小，容易爆掉。
* BFS (廣度優先)：不會爆，因為它用的是 「記憶體堆積 (Heap)」，這個空間很大（通常是電腦的 RAM）。
* DSU (並查集)：不會爆，因為它主要是操作 「陣列」，幾乎不需要遞迴，路徑非常短。

---

### 程式碼 BFS版本
如果要改成BFS，可以延續剛剛寫的版本，只把dfs函式改成bfs函式，其他的都不用改
:::info
BFS的核心是queue
:::

int bfs(int start_y, int start_x) {
    queue<pair<int,int>> q; //主要核心queue
    
    // 把起點放進去
    q.push({start_y, start_x});
    visited[start_y][start_x] = 1;
    
    int count = 0; // 紀錄數量

    while(!q.empty()) { //只要queue中還有數，就繼續做
        // 1. 拿出排頭
        pair<int,int> curr = q.front();
        q.pop();
        count++; // 算一格

        int cy = curr.first;
        int cx = curr.second;

        // 2. 往四周蔓延
        for(int k=0; k<4; k++) {
            int ny = cy + dy[k];
            int nx = cx + dx[k];

            // 邊界檢查
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

            // 接通檢查 (沒走過 + 能接通)
            if(grid[ny][nx]!='0' && visited[ny][nx]==0 && canconnect(grid[cy][cx], grid[ny][nx], k)) {
                visited[ny][nx] = 1; // 立刻設成已經拜訪，避免重複加入
                q.push({ny, nx}); //這裡不是呼叫 dfs，而是「加入隊伍」
            }
        }
    }
    return count;
}

---
### 並查集 (Disjoint Set Union) 版本
這也是他們提出的一個方法，我覺得解這種問題很適合

#include<bits/stdc++.h>
using namespace std;

//全域變數
char grid[600][600]={"0"}; //地圖
int visited[600][600]={{0}}; //是否走過 0為沒走過
int n,m;

map<char,vector<bool>> pipetype={ //定義每個水管的開口：上, 下, 左, 右
//       上     下     左     右
{'I', {true,  true,  false, false}},
{'H', {false, false, true,  true }},
{'L', {true,  false, false, true }},
{'J', {true,  false, true,  false}},
{'7', {false, true,  true,  false}},
{'F', {false, true,  false, true }},
{'X', {true,  true,  true,  true }}
};

//偏移量   上 下 左 右
int dx[4]={0,0,-1,1}; 
int dy[4]={-1,1,0,0};
int op[4]={1,0,3,2};// 這是反方向，例如我要找目前跟上方的管子k=0對到map的上，此時op[k]=1 對應到map的下


// DSU 結構
struct DSU {
    vector<int> parent;// parent[i]=i的老大是誰(會指向最上層的)
    vector<int> sz; // 用來紀錄每個老大底下有多少小弟(包含自己)

    DSU(int total_nodes) { //建構子寫法，在宣告這個struct的時候會一併執行，把初始值設定好
        parent.resize(total_nodes);
        sz.resize(total_nodes, 1); // 一開始大家都是 1 個人(沒有小弟)
        for(int i=0;i<total_nodes;i++) parent[i] = i; // 一開始大家都是自己的老大
    }

    int find(int x) {
        if (parent[x] == x) return x; //自己就是最上層老大，回傳自己
        //下面三行是路徑壓縮(把樹壓縮成兩層)
        int root=find(parent[x]);//遞迴找最上層的老大
        parent[x]=root;//更新我的老大(直接指向最上面的人)，方便下次查
        return root;
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) { //x和y的老大是不同人
            parent[rootX] = rootY; // 把 x接到 y 下面，y變成老大
            sz[rootY] += sz[rootX]; // Y 的人數增加了 X 的人數
        }
    }
};

bool canconnect(char a, char b, int k) {
    return pipetype[a][k] && pipetype[b][op[k]];
}

int main() {
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    DSU dsu(n * m);//建立 DSU，總節點數是 n * m
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '0') continue;
            int current_id = i * m + j; //因為DSU是一維的工具，所以我需要把二維座標轉成一維的獨特編號，公式:i(列) * m(寬度) + j(行)
            for (int k = 0; k < 4; k++) {//嘗試往四周蔓延
                int ny = i + dy[k];
                int nx = j + dx[k];
                int neighbor_id = ny * m + nx;
                if (ny >= 0 && ny < n && nx >= 0 && nx < m && grid[ny][nx] != '0') { //目標格子在便藉內且不是0
                    if (canconnect(grid[i][j], grid[ny][nx], k)) {//有連通
                        dsu.unite(current_id, neighbor_id);
                    }
                }
            }
        }
    }

    // 最後掃描一遍，找出最大的 size
    int max_ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '0') {//過濾掉空地
                int id = i * m + j;
                if (dsu.parent[id] == id) {// 只看老大身上的 size
                    max_ans = max(max_ans, dsu.sz[id]);
                }
            }
        }
    }
    cout << max_ans << endl;
}

這個版本就成功通過全部測資了，如果有其他想法歡迎一起討論~

---

[TOC]