Theseus and the Minotaur

Those of you with a classical education may remember the legend of Theseus and the Minotaur. This is an unlikely tale involving a bull headed monster, an underground maze full of twisty little passages all alike, love-lorn damsels and balls of silk. In line with the educational nature of this contest, we will now reveal the true story.

The maze was actually a series of caverns connected by reasonably straight passages, some of which could only be traversed in one direction. In order to trap the Minotaur, Theseus smuggled a large supply of candles into the Labyrinth, as he had discovered that the Minotaur was afraid of light. Theseus wandered around somewhat aimlessly until he heard the Minotaur approaching along a tunnel. At this point he lit a candle and set off in pursuit. The Minotaur retreated into the cavern it had just left and fled by another passage. Theseus followed, slowly gaining, until he reached the k'th cavern since lighting the candle. Here he had enough time to place the lighted candle in the middle of the cavern, light another one from it, and continue the chase. As the chase progressed, a candle was left in each k'th cavern passed through, thereby limiting the movement of the Minotaur. Whenever the Minotaur entered a cavern, it would check the exits in a particular order, fleeing down the first that did not lead directly to a lit cavern. (Remember that as Theseus was carrying a lit candle, the Minotaur never exited a cavern by the tunnel used to enter it.) Eventually the Minotaur became trapped, enabling Theseus to defeat it.

Consider the following Labyrinth as an example, where in this case the Minotaur checks the exits from a cavern in alphabetical order:

Assume that Theseus is in cavern C when he hears the Minotaur approaching from A, and that for this scenario, the value of k is 3. He lights a candle and gives chase, pursuing it through A, B, D (leaves a candle), G, E, F (another candle), H, E, G (another), H, E (trapped).

Write a program that will simulate Theseus's pursuit of the Minotaur. The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them, followed by the identifiers for the caverns which the Minotaur and Theseus were in when contact was first made, followed by the value of k. If a cavern has no exit it may or may not be in the input.

Input

Input will consist of a series of lines. Each line will describe a scenario in the format shown below (which describes the above example). No line will contain more than 255 characters. The file will be terminated by a line consisting of a single #.

Output

Output will consist of one line for each Labyrinth. Each line will identify the lit caverns, in the order in which the candles were left, and the cavern in which the Minotaur was trapped, following the format shown in the example below.

Sample input

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

Sample output

D F G /E

---

題目不是很好理解，簡單說是一個尾隨遊戲。

由於那個牛頭怪會依序檢查他的地下迷宮，檢查的方式類似於 dfs，也就是說走訪所有可能按照字典順序，不過由於尾隨的勇者每走 K 步會放下一個蠟燭，使得牛頭怪無法在此走到那格，因此牛頭怪最後會只剩下一個地方可走，最後被困住。

問最後牛頭怪的位置，以及放蠟燭的幾個位置。

#include <stdio.h>
#include <string.h>
int g[26][105], gt[105], K;
int candle[26], found, putorder[10005], pidx;
void dfs(int M, int T, int step) {
    if(found == 1)
        return;
    if(step == K) {
        candle[M] = 1;
        putorder[pidx++] = M;
        step = 0;
    }
    int i, runnable = 0;
    for(i = 0; i < gt[M]; i++) {
        if(g[M][i] != T) {
            if(candle[g[M][i]] == 0) {
                dfs(g[M][i], M, step+1);
                runnable = 1;
            }
        }
    }
    if(runnable == 0) {
        found = 1;
        if(step == 0)   pidx--;
        for(i = 0; i < pidx; i++)
            printf("%c ", putorder[i]+'A');
        printf("/%c\n", M+'A');
    }
}
int main() {
    char s[1024];
    int i, x , y;
    while(gets(s)) {
        if(s[0] == '#') break;
        memset(gt, 0, sizeof(gt));
        for(i = 0; s[i]; i++) {
            x = s[i]-'A', i++, i++;
            while(s[i] != ';' && s[i] != '.') {
                y = s[i]-'A';
                i++;
                g[x][gt[x]++] = y;
            }
            if(s[i] == '.') break;
        }
        char M[20], T[20];
        sscanf(s+i+1, "%s %s %d", M, T, &K);
        memset(candle, 0, sizeof(candle));
        found = 0, pidx = 0;
        dfs(M[0]-'A', T[0]-'A', 1);
    }
    return 0;
}