UVa10507 - Waking up brain(BFS)

題目大意：

近代的研究指出如果要喚醒腦袋的區域時，必須要附近三塊的腦袋都是清醒的狀況才有辦法喚醒此區域，我們會給你已經清醒的區域，還有哪些區域是有連結的，想請問多久後才可以將腦袋中所有區域喚醒成功？

P.S. 喚醒需要一年的時間，請輸出多久可以喚醒，如果沒辦法喚醒輸出 “THIS BRAIN NEVER WAKES UP”，可以就輸出 “WAKE UP IN, n, YEARS”, where n is the number of the years all the brain has taken to wake up

題目連結

重點觀念

• 必須要看懂英文，這題對我來說英文有點難QQQ
• 觀察出此題類似於 BFS，但都只跑一層
• 哪些節點可以被喚醒再跑一次第二點。

分析

這題與 BFS 比較不同的地方就是加入節點的要求是需要有鄰近 3 個區域被喚醒才可以被加入節點，為了要解決這個問題，我們開一個陣列叫做 area，每次讓喚醒的區域連結到還在睡著的區域，就讓被睡著的區域加一，如果加到 3 就加入節點，做下一次的 BFS。

QUESTION: 那要怎麼找出是需要幾年可以把全部區域喚醒呢

這時候就需要遞迴來幫助我們了，我們 BFS 的 vector (定義 vA)是當前有被喚醒的區域，裡面的節點都成功去 link 每個未喚醒的節點後就 pop，那如果有節點在此時被喚醒我們則把她加入到新的 vector 中(定義 vB)，當 vA 全部完成後，如果 vB 有節點我們就進行下一次的 BFS，使用遞迴則是可以方便知道我們總共喚醒幾次。

只需要將每一次的遞迴視為明年會被激活的區域即可。特別注意的是，一開始的區域不可以被 +1，因為那是已經醒來的區域，因此在進入遞迴時先將值設為 -1，這樣進入第一層遞迴時就會歸零。

QUESTION: 但上面那個問題沒有解決怎麼知道全部的區域都被喚醒呢？

我們一開始不是有一個陣列(area) 可以知道此區域有幾個喚醒的區域連結嗎？我們只需要寫一個迴圈查詢所有的節點是不是都有 3 個或 3 個以上的區域連結就可以檢查了！

心得

這題其實不難，但蠻酷的，有一些很簡單的腦筋急轉彎需要去思考，遞迴裡面塞入一個 BFS，似乎有點類似於 IDDFS，但年代久遠我有點忘記了QQ，還需要在去複習一下，寫演算法很容易會忘記QQ，希望我的腦袋可以把這些思維都記錄下來並應用在生活上，這樣我就會是一個很不賴的人了！

希望自己的大腦要能夠一直都醒來拉，不醒來會對周遭的人很麻煩，會麻煩到他們的。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

裡面為了讓程式碼更好寫，有做一些小手腳，在這邊會加上一些定義，供大家在閱讀時更好閱讀

• -INF 已經有被掃描過的區域
• flag 判斷有多少節點是喚醒的
• ca, cb 輸入題目中的邊時要用到的字元

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 30
#define INF 0x3f3f3f //-INF 表示此節點已經被掃描過
using namespace std;
int n, m, cnt, flag;
int area[MAXN];
string temp;
char ca, cb;
vector<int> edge[MAXN]; //每一個邊，第一個維度是分類為 edge[i] 可以連接到哪些邊


void init(){ //將所有的陣列清空，不被上次的測資干擾
    memset(area,0,sizeof(area)); //清空所有的 area
    for(int i = 0; i < MAXN; i++) edge[i].clear(); //清空所有的邊
}

void wake(vector<int> record){ // BFS遞迴，查詢喚醒次數跟讓上次被喚醒的區域再跟其他區域連結 
    vector<int> temp2; //這次經過連結後會被喚醒的區域先暫存的 vector
    cnt++;
    for(auto it: record){ //將上次被喚醒的區域去跟其他節點連結
        //cout << (char)(it+'A') << ' ';
        for(int i = 0; i < edge[it].size(); i++){ //每一個邊連結的其他邊
            area[edge[it][i]]++; //被連結的其他區域 +1，表示鄰近被喚醒的區域 +1
            if(area[edge[it][i]] >= 3){ //如果大於 3，表示下次這個區域可以被喚醒
                temp2.push_back(edge[it][i]); //先放入暫存 vector
                area[edge[it][i]] = -INF; //此節點被放入 vector 了，因此設為 -INF
            }
        }
    }
    //cout << '\n';
    if(temp2.empty()) return ; //如果是空的就表示已經沒有區域被喚醒，沒辦法在跟其他區域連結
    return wake(temp2); //還有區域被喚醒，因此進入下次的遞迴在跟其他區域連結
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> m){
        vector<int> record; //紀錄有被喚醒的區域
        init(); //初始化，清空

        cin >> temp; //輸入字串，為一開始有被喚醒的區域
        for(int i = 0; i < temp.length(); i++){ 
            record.push_back(temp[i] - 'A'); //將被喚醒的區域加入 vector，等等 BFS
            area[temp[i] - 'A'] = -INF; //點被加入 vector，因此值設為 -INF
        }
        for(int i = 0; i < m ; i++){ //輸入連結的邊
            cin >> ca >> cb;
            edge[ca - 'A'].push_back(cb - 'A'); //hash 透過 ascii，A = 0, B = 1,...
            edge[cb - 'A'].push_back(ca - 'A'); //雙向連結，題目有說明是雙向邊
        }
        cnt = -1; flag = 0; //cnt = -1，第一次的區域是已經醒來，所以不需要等待
        //flag 是要查詢哪些區域有被喚醒且已經被掃描過，如果有被喚醒就一定會被掃瞄，BFS 會做好這件事
        wake(record);
        for(int i = 0; i < MAXN; i++){ //查詢所有區域是否有被喚醒且已經被掃描過
            if(area[i] < 0) flag++; //有就 flag++
            //cout << area[i] << '\n';
        }


        if(flag == n) cout << "WAKE UP IN, " << cnt << ", YEARS\n";
        //表示有被喚醒且已經被掃描過區域等同題目給的所有區域也就是所有區域都被喚醒，因此可以輸出 cnt，代表只需要 cnt 年就可以將腦袋全部區域喚醒
        else cout << "THIS BRAIN NEVER WAKES UP\n"; 
        //表示所有區域並沒有都被喚醒且已經被掃描過，有些區域沒有被喚醒，因此輸入永遠沒辦法讓大腦醒來 QQ。
    }

    return 0;
}