題目： UVa - 168 - Theseus and the Minotaur

題目說明

有一個迷宮，一個勇者跟一個怪物，怪物會怕光，所以勇者拿著蠟燭在追逐怪物，勇者每走一定的步數後會插上蠟燭，並繼續走，所以怪物一定會被逼到無路可走，求勇者有插上蠟燭的地方及最後怪物被抓到的地方。在每個地點怪物都會優先往字典序小的地方走。

Input： 一組測資為一行字串，前面為每個地點能繼續往下走的地點 ( 單向 )，後面為兩個字元及一個數字，分別代表怪物一開始的位置及勇者一開始的位置及勇者每走幾步會插上蠟燭。勇者一開始一定會在怪物的附近一個點。

Output： 勇者插上蠟燭的地方及怪物最後被抓到的地方。

解題思路

讀取資料後先建立圖，遍歷字串，若碰到 ':' 代表前面一個字元為某個地點，後面接的是某個地點能繼續往下走的地點，直到遇到 ';' 或 '.' 為止。定義 candle 紀錄插上蠟燭的位置，steps 為勇者走的步數，M 為怪物當前的位置，T 為勇者當前的位置，之後 DFS 求解即可，先判斷是否插上蠟燭，接著找怪物能繼續往下走的位置，若有可以走的地方則 M 更新為該位置，T 更新為原本 M 的位置，否則代表怪物無路可走。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <functional>
#include <vector>
#include <string>

#define SIZE(c) int(c.size())
#define diff(ch) (ch - 'A')

using namespace std;

// reference: https://ppt.cc/fMYpGx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    string str;

    while (cin >> str && str != "#")
    {
        int k;
        char m, t;
        cin >> m >> t >> k;

        // 讀取資料並建立圖
        vector<int> G[26];
        auto read = [&](int j) { return str[j] != ';' && str[j] != '.'; };
        for (int i = 0; i < SIZE(str);)
        {
            if (str[i] == ':')
            {
                int j = i + 1;
                while (read(j)) G[diff(str[i - 1])].push_back(diff(str[j++]));
                i = j + 1;
            }
            else ++i;
        }

        int steps = 0;
        int candle[26] = {};

        function<void(int, int)> dfs = [&](int M, int T)
        {
            // 放蠟燭
            if (steps && steps % k == 0) cout << char(T + 'A') << " ", candle[T] = 1;

            auto& v = G[M];
            for (int i = 0; i < SIZE(v); ++i)
            {
                // 如果 v[i] 沒有蠟燭且 t 不在 v[i] 那 M 就可以往 V[i] 走
                if (v[i] != T && !candle[v[i]])
                {
                    ++steps;
                    dfs(v[i], M);
                    return;
                }
            }

            // 如果 m 無路可走，代表會在 M 被抓到
            cout << '/' << char(M + 'A') << '\n';
        };

        dfs(m - 'A', t - 'A');
    }
}

參考資料

ACM Plan UVa - 168 Theseus and the Minotaur(图的遍历，深度优先)