UVa168 - Theseus and the Minotaur (DFS)

題目大意：

英雄要捕捉牛頭怪，牛頭怪怕光也怕英雄，給你一張圖(有節點與邊)，英雄可以在 K 步後的節點蠟燭，這樣牛頭人就不會在往那通道走，總有一天英雄會抓到牛頭人，我們想請問牛頭人最後走到哪裡就無路可走。

牛頭人走路有順序性，一定會先走字典序最小的值，但不會回頭走。
英雄一開始一定在牛頭人旁邊的節點，也就是英雄與牛頭人的距離只有 1 (只有一個邊)。

題目輸入極其難受，請仔細思考
P.S. 注意 K 沒有限制，想要多大都可以，但基本上可以不需要在意這個問題。

分析

這裡主要有兩點需要特別注意，由於 K 數字沒有極限，但是這題目的 K 基本上暴力是可以通過，不需要做 mod，但如果要 mod 就會變成 NP 問題，雖然 mod 出來的數字與 K 相同，但是英雄的位置則不一定相同，回推就會不同，輸出的路徑也就不一定相同。

基本上就是紀錄遇到 K 時就紀錄這個節點，直到沒辦法再繼續 DFS 時最後的那個節點就是牛頭人無處可逃的地方，但是需要記得一件事情因為 K 沒有限制，但遞迴最多只能向下深層 9998，再往下就會 stack overflow(不是你想的那個論壇，就實際上的名字)，因此要將遞迴 DFS 改成迴圈 DFS，也就是把繼續遞迴的地方改成 break 模擬遞迴。

輸入格式

由於題目的輸入格式與眾不同，是 A 節點配上 ‘:’(冒號) 在加上後面全部的所有字元，假設 A:BCD，那就是 A 連接 B ,A 連接 C,A 連接 D。

我的想法是先將前面那行輸入成 String，接下來則用 flag 當作標誌

• flag = 0
  表示讀到 ‘:’(冒號)，因此我們找 ‘:’(冒號) 的前一字元即可，同時將 flag = 1，由於題目有說明一個節點只會有英文字母才能這樣做
• flag = 1
  為 ‘:’(冒號) 後面的所有的值，因此將 vector[A].push_back(b)，b 為 : 後的所有值
• 讀到 ‘.’(句號) 或 ‘;’(分號)
  讀到 ‘.’(句號) 或 ‘;’(分號) 這裡時，就換成下一個 A 節點，因此 flag 設 0 換設定下一個節點與其他節點的連結

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 300
#define MAXN_Alpha 27
using namespace std;
string strQ  ;
char strM , strT ;
int M , T , K , ans , cnt ; //cnt is all of use letter
int flag , nx , ny; //nx nodex ny nodey
int visit[MAXN];
vector<int> record ;
vector<int> path[MAXN_Alpha] ;
int dfs(int m , int t , int k ){
    int flag = 1 ;
    while(1){
        flag = 1 ;
        if(k == 0 ){ 
            visit[t] = 1 ;
            record.push_back(t) ;
            //cout << "candle is " << (char)(t+'A') << '\n' ;
            k = K ;
        }
        //cout << "m is " << (char)(m+'A') << '\n' ;
        for(auto it : path[m]){ //DFS
            if((visit[it] == 0 && it != t) ){ // recursive -> break
                //cout << i << '\n' ;
                flag = 0 ;
                t = m ;
                m = it ;
                k-- ;
                break ;
            }
        }
        if(flag) break;
    }
    return m;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    while(cin >> strQ && strQ != "#"){
        cin >> strM >> strT >> K ;
        T = strT - 'A' ;
        M = strM - 'A' ;
        //cout << T << ' ' << M << ' ' << K << '\n' ;
        flag = 0;
        cnt = 0 ;
        memset(visit,0,sizeof(visit));
        record.clear();
        for(int i = 0 ; i < MAXN_Alpha ; i++)
            path[i].clear();
        for(int i = 0 ; i < strQ.length() ; i++){
            if(flag == 0 && strQ[i] == ':'){
                cnt ++;
                nx = strQ[i-1] - 'A' ;
                flag = 1 ;
            }
            else if(strQ[i] == '.' || strQ[i] == ';'){
                flag = 0 ;
            }
            else if(flag == 1 ){
                ny = strQ[i] - 'A' ;
                path[nx].push_back(ny);
                //cout << "edge is " << nx << ' ' << ny << '\n' ;
            }
        }
        //K %= cnt ;
        //if(K == 0 ) K = cnt ;
        ans = dfs(M,T,K);
        for(auto it : record )
            cout << (char)( 'A' + it) << ' ' ;
        cout << '/' << (char)( 'A' + ans) << '\n'  ;
    }


    return 0;
}