题目：忒修斯和牛头人，这是个很有名的古希腊神话故事。题目的描述也不是一般的长啊。
估计很多人是被英文吓跑了，╮(╯▽╰)╭为了干掉他，看了3天的题目。
题目大概的意思：这有一个迷宫，由山洞和隧道组成，T（忒修斯）和M（牛头人）开始时
处于迷宫的隧道中，然后向前走。T的运动规则是，进入到一个洞穴后，就靠着右侧的强走，
就是走到他来的那个洞口的逆时针的下一个洞口处；如果这个隧道没走过，他就标记一下，
然后沿着它向前走，如果标记过，他就寻找逆时针顺序的下一个隧道口。M的运动规律相反，
他是靠左侧走的，也就是顺时针的选取隧道口，标记则跳过，没标记就标记，然后走进去。
如果，他们在同一个山洞相遇，那么T就杀死M；如果，他们在隧道相遇，那么M就杀死T。
如果T走进的山洞，发现M在他之前走过，那么他就会在这个山洞中点燃一根蜡烛；然后，
沿着M最后走过的隧道前进。如果M走进山洞时，发现有蜡烛，他就退回到上一个山洞。
求最后谁杀了谁（题目的数据满足，他们一定相遇）。
分析：模拟。数据利用双线链表储存，可双向读取。这种题目的难点就是划分子操作。
开始时，我尝试划分成两个子操作：
1.move_caverns_T（a，b），T从a山洞，移动到b山洞。
2.move_caverns_M（a，b），M从a山洞，移动到b山洞。
这样对于T，M都需要记录之前的节点和当前选择的隧道。
这样划分的问题就是：判断在隧道相遇有困难。所以想到下面的划分形式：
1.move_caverns_to_passage_T（a，b），T从a移动到ab间的隧道中。
2.move_caverns_to_passage_M（a，b），M从a移动到ab间的隧道中。
3.move_passage_to_caverns_T（a，b），T从ab间的隧道中移动到b。
4.move_passage_to_caverns_M（a，b），M从ab间的隧道中移动到b。
每次运行的顺序是：（a，b先后顺序无所谓，d，e的先后顺序无所谓）
a.move_passage_to_caverns_T（a，b）
b.move_passage_to_caverns_M（a，b）
c.判断M和T是不是在一个洞穴，是则M被杀
d.move_caverns_to_passage_T（a，b）
e.move_caverns_to_passage_M（a，b）
f.判断M和T是不是在同一个隧道中，是则T被杀任何一种有解的数据，都可以用上面的序列求解，初始在隧道相遇除外（需要特判）。
#include <iostream>
#include <cstdlib>
#include <cstdio>
typedef struct dnode
{
int point;
int flag1;//标记T走过，取值0和1
int flag2;//标记M走过，取值>0，表示访问顺序
dnode* left;
dnode* right;
}dlink;
dlink Node[2000];
dlink* Head[30];
int d_size;
void dlink_inital( void )
{
d_size = 0;
for ( int i = 0 ; i < 26 ; ++ i )
Head[i] = NULL;
}
void dlink_add( int a, int b )
{
if ( !Head[a] ) {
Node[d_size].left = &Node[d_size];
Node[d_size].right = &Node[d_size];
Head[a] = &Node[d_size];
}else {
Node[d_size].right = Head[a];
Node[d_size].left = Head[a]->left;
Head[a]->left->right = &Node[d_size];
Head[a]->left = &Node[d_size];
}
Node[d_size].flag1 = 0;
Node[d_size].flag2 = 0;
Node[d_size].point = b;
d_size ++;
}
//计算下一个隧道位置
dlink* dlink_next( dlink* p, int id, int forword )
{
dlink *t = Head[p->point];
while ( t->point != id )
t = t->right;
return (forword?t->right:t->left);
}
//返回M最近走过的隧道
dlink* dlink_last( dlink* p )
{
dlink *t = p,*m = p,*q;
for ( q = t->right; t != q ; q=q->right )
if ( m->flag2 < q->flag2 )
m = q;
return m;
}
//标记M到过(2)，或者点燃蜡烛(1)
int visit[30];
int main()
{
char a,b,c,d;
while ( ( a = getchar() ) != ‘#‘ ) {
dlink_inital();
while ( a != ‘@‘ ) {
getchar();
while ( ( b = getchar() ) != ‘\n‘ )
dlink_add( a-‘A‘, b-‘A‘ );
a = getchar();
}
a = getchar();b = getchar();
c = getchar();d = getchar();
getchar();
if ( ( a == c && b == d ) || ( a == d && b == c ) ) {
printf("Theseus is killed between %c and %c\n",a,b);
continue;
}
for ( int i = 0 ; i < 26 ; ++ i )
visit[i] = 0;
int T = a-‘A‘,M = c-‘A‘,S;
dlink *p = Head[a-‘A‘];
while ( p->point != b-‘A‘ ) p = p->right;
dlink *q = Head[c-‘A‘];
while ( q->point != d-‘A‘ ) q = q->right;
int flagp = 1,flagq = 1,Mmark = 1;
while ( 1 ) {
//Minotaur into cavern
S = M;
M = q->point;
q = dlink_next( q, S, 0 );
if ( visit[M] == 1 ) {
q = dlink_next( q->right, M, 0 );
M = S;
}else visit[M] = 2;
//Thseus into cavern
S = T;
T = p->point;
p = dlink_next( p, S, 1 );
if ( T == M ) {//meet in cavern
printf("The Minotaur is slain in %c\n",M+‘A‘);
break;
}
//Thseus into passage
if ( visit[T] == 2 ) {
visit[T] = 1;
p = dlink_last( p );
}else while ( p->flag1 ) p = p->right;
p->flag1 = 1;
//Minotaur into passage
while ( q->flag2 ) q = q->left;
q->flag2 = Mmark ++;
if ( M == p->point && T == q->point ) {//meet in passage
printf("Theseus is killed between %c and %c\n",‘A‘+T,‘A‘+M);
break;
}
}
}
return 0;
}
UVa 243 - Theseus and the Minotaur (II),布布扣,bubuko.com
UVa 243 - Theseus and the Minotaur (II)
原文：http://blog.csdn.net/mobius_strip/article/details/22325429