Posted on 2010-03-05 13:24
Uriel 阅读(355)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
搜索
简单的BFS，不过输入有点搞。。见Discuss可知数据可能有循环。。
一开始用scanf %s 读入怎么都错。。改成%c读入就过了。。不知道什么原因。。也许是句子里也能有连续一个以上空格？
/**//*
Problem: 2023 User: Uriel
Memory: 200K Time: 0MS
Language: C++ Result: Accepted
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
int cnt;
int c[2];
char k;
char str[10];
char word[300];
};
node P[110];
int cse,t,n,l,r,flag;
int vis[110],que[110],res[110];
int main()
{
// freopen("out.txt","w",stdout);
int i,j,k;
scanf("%d",&cse);
t=1;
while(cse--)
{
memset(P,0,sizeof(P));
memset(que,0,sizeof(que));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
getchar();
P[i].k=getchar();
getchar();
k=0;
if(P[i].k=='C')
{
getchar();
for(j=0;;j++)
{
P[i].word[j]=getchar();
if(P[i].word[j]=='\"')break;
}
scanf("%d %d",&P[i].c[0],&P[i].c[1]);
}
else
{
getchar();
for(j=0;;j++)
{
P[i].word[j]=getchar();
if(P[i].word[j]=='\"')break;
}
scanf("%s",P[i].str);
}
}
l=0;
r=1;
flag=0;
que[1]=1;
memset(vis,0,sizeof(vis));
vis[1]=0;
while(l!=r && !flag)
{
l++;
if(P[que[l]].k=='C')
{
int tmp1=P[que[l]].c[0];
int tmp2=P[que[l]].c[1];
if(!vis[tmp1])
{
que[++r]=tmp1;
vis[tmp1]=que[l];
}
if(!vis[tmp2])
{
que[++r]=tmp2;
vis[tmp2]=que[l];
}
}
else
{
if(strcmp(P[que[l]].str,"HAPPY")==0)flag=1;
}
}
printf("STORY %d\n",t++);
k=0;
while(que[l])
{
res[++k]=que[l];
que[l]=vis[que[l]];
}
for(i=k;i>=1;i--)
{
for(j=0;;j++)
{
if(P[res[i]].word[j]=='\"')break;
else
printf("%c",P[res[i]].word[j]);
}
printf("\n");
}
}
system("PAUSE");
return 0;
}