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

题目：

原文太长，简单说一下。如标题所述，是希腊神话的迷宫故事，给出一张图，以及T和M两个人物的位置。因为M怕光，所以T拿着蜡烛追逐M，T每走过K个节点，就会在第K个节点上点上一支蜡烛。M在逃跑时，会按照预先给出的路线进行选择（按字母表顺序）。M不会选择有T在的节点和有蜡烛的节点，最终M一定会被T追到。

多个样例，每个样例为一行字符串，不超过255个字符，只有一个’#'号的行为结束标志，不处理。

每行样例包括了M在每个节点的选择顺序，样例最后给出M和T的初始位置，以及K值。

输出追逐过程中摆放蜡烛的节点以及M被追到时的节点。格式参考样例。

输入样例

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3

输出样例

D F G /E

解析

UVA一如既往的屑输入输出格式-.-

记录好T走过的节点数，为K的倍数时，在当前节点放上蜡烛。M无路可走时，M所在的节点就是终点。

简单的深度优先问题，注意输出顺序。坑点在于K可能会很大，可能超过100w，所以如果用递归会爆栈，改成用数据结构模拟深度优先即可。

代码

榜上最快40ms，1248B，我这个50ms，1152B，可以改进一下这个冲击榜一233

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
typedef vector<char> vc;
vector<vc> arr(26);
int k;
int book[26];
stack<char> sk;
void dfs(char m, char t){
    stack<char>().swap(sk);sk.push(t);int i;while(!sk.empty()){
    int cnt = sk.size() - 1;//减去初始节点if(cnt > 0 && cnt % k == 0){
    printf("%c ", sk.top());book[sk.top() - 'A'] = 1;//放蜡烛}vc &v = arr[m - 'A'];for(i = 0; i < v.size(); i++){
    if(v[i] != sk.top() && book[v[i] - 'A'] == 0){
    sk.push(m);//更新T的位置m = v[i];break;}}if(i == v.size()){
    printf("/%c\n", m);break;}}return ;
}
int main(){
    // freopen("i.txt", "r", stdin);// freopen("o.txt", "w", stdout);char s[256];char M, T;while(gets(s)){
    if(s[0] == '#') break;memset(book, 0, sizeof(book));arr.assign(26, vc());for(int i = 0; s[i];){
    //输出处理部分if(s[i] == ':'){
    char a = s[i - 1];int j = i + 1;while(s[j] != ';' && s[j] != '.')arr[a - 'A'].push_back(s[j++]);i = j + 1;}else if(s[i] == ' '){
    M = s[i + 1];T = s[i + 3];sscanf(s + i + 4, "%d", &k);break;}else i++;}dfs(M, T);}
}