UVa208 - Firetruck (雙向搜尋-逆向搜尋)

題目大意：

在一個區域中必定會有一個消防局，現在有一個點失火，我們想知道從消防局到失火點的所有路徑，並且輸出。
請注意：消防員不願意接受繞圓此動作(繞了一個圓圈再回到某個點，即形成一個循環)，因為會影響他們的行進速度。

題目測資的點不會超過 22 個點，也就是路徑最多不會超過 22 條路徑。

分析：

這題是使用雙向搜尋是最適合的題目之一，由於此題目必須要輸出每一個路徑，因此用 brute force 是最好的應用，但如果想到這邊然後就直接進行 DFS or BFS 搜尋就會遇到一個大麻煩，時間 TLE。

為甚麼會遇到 TLE 呢？我們舉個例子：我們假設道路都是單行道，只能向北走，想請問有沒有辦法從台北走到高雄？

答案是不行的，因為道路都是單行道且只能往北走台北往到高雄勢必是不可能，但程式會不斷嘗試的從台北出發往北的道路不斷進行搜尋，因此在道路複雜許多後就會造成 TLE 的問題，這時候就要用到一個觀念，雙向搜尋。

雙向搜尋-同時搜尋

我們先從終點進行搜尋(反向搜尋)，透過終點搜尋(BFS,DFS)可以接觸到的所有節點，並記錄下來；之後再透過起點進行搜尋(正向搜尋)，在正向搜尋時再附加一個條件為必須要是反向搜尋有經過的節點，才可以確保目前正向搜尋的路線中是正確的方向，而不是在往錯誤的方向前進。

這裡我們則使用 DFS 進行撰寫。

QUESTION: 為甚麼要這樣寫呢？這樣不是把兩張一樣的圖搜尋過一遍嗎

這個問題問得很好，我與我的演算法隊友齊笎經過一番論戰過後，找出原因，測試資料中有一筆測資是起點並沒有與終點連在一起，也就是他們是兩張分開的圖，其他的點則交互連在一起。

如果沒有這個反向 dfs 就會導致起點不斷的進行搜尋卻怎麼樣都沒有搜尋到終點，當測資一大時就會超時，極端的測資是 終點自己一個點，然後起點與其他點都互相連接，即每個點都有 n-2 個邊。扣掉終點與自己

void reverse_dfs(int u ){ //反向搜尋
    join[u] = 1 ; //join 紀錄反向搜尋會經過的點，1表示會經過
    for(int i = 1 ; i < MAXN ; i++)
        if( !join[i] && road[u][i] ) reverse_dfs(i);
        //road 表示這條路徑目前已經被用過
}

焦點回到題目上，解開題目的小設計

之後只需要做好每一次在讀取測試資料時要清除上筆測試的資料且題目輸出格式正確，輸出的路徑那行最後不可以有空白，即1 3 5，以及不要將 DFS 寫爛即可。

參考連結

UVa 208 – Firetruck [双向DFS]

心得

雙向搜尋是我這一周碰到的新觀念，觀念雖然是簡單但其實如果用在題目上，我還會傻住，這也驗證了演算法一向都是觀念好懂，實作很難的事物阿，希望我之後可以善用此演算法在未來或是大型的演算法比賽中。

題目程式碼

其實就是沒有附上說明的程式碼，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 22
using namespace std;
int n , kase , cnt , vis[MAXN] , road[MAXN][MAXN] , join[MAXN];
vector<int> res ;

void reverse_dfs(int u ){
    join[u] = 1 ;
    for(int i = 1 ; i < MAXN ; i++)
        if( !join[i] && road[u][i] ) reverse_dfs(i);
}

void dfs(int u ){
    if(u == n ){ //到達終點，輸出路徑
        for(int i = 0 ; i < res.size()-1 ; i++) cout << res[i] << ' ' ;
        cout << res[res.size()-1] ;
        cout << '\n' ;
        cnt++ ;
        return ;
    }
    for(int i = 1 ; i < MAXN ; i++){ 
        if(!vis[i] && road[u][i] && join[i] ){ //符合條件後記錄節點 
            vis[i] = 1 ;
            res.push_back(i);
            dfs(i);
            res.pop_back();
            vis[i] = 0 ;
        }
    }
}

void init(){ //清除資料並重新整理
    memset(road,0,sizeof(road));
    memset(vis,0,sizeof(vis));
    memset(join,0,sizeof(join));
    cnt = 0 ;
    res.clear();
    vis[1] = 1 ;
    res.push_back(1) ;
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout) ;
#endif // LOCAL
    int a,b ;
    while(cin >> n){
        init();
        while(cin >> a >> b && a && b ){ 
            road[a][b] = 1 ; road[b][a] = 1 ; //紀錄路徑
        }
        reverse_dfs(n);
        cout << "CASE " << ++kase << ":\n" ;
        dfs(1);
        cout << "There are " << cnt << " routes from the firestation to streetcorner " << n << ".\n";
    }

    return 0;
}

紙筆紀錄

上方有一點提到我與齊笎進行探討，我將我們在那邊進行廝殺的紀錄放在此處，留念XD。