hdu 1354
12914 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1354
考え方:最も面倒なのは文字列の処理ですが、sscanf関数の機能はかなり強くて、orz....それからdfsでいいですが、18人しかいません.
View Code
考え方:最も面倒なのは文字列の処理ですが、sscanf関数の機能はかなり強くて、orz....それからdfsでいいですが、18人しかいません.
View Code
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<string>
6 using namespace std;
7 #define MAXN 333
8 struct Node{
9 int f1,f2;
10 }C[MAXN];
11 char str[MAXN];
12 int path[MAXN];
13 bool mark[MAXN];
14 int p;
15 struct Page{
16 int tag;
17 string str;
18 }Text[MAXN];
19
20 bool dfs(int page){
21 path[p++]=page;
22 if(Text[page].tag==2)return true;
23 if(Text[page].tag==1)return false;
24 int next1=C[page].f1;
25 int next2=C[page].f2;
26 if(!mark[next1]){
27 mark[next1]=true;
28 if(dfs(next1))return true;
29 p--;
30 }
31 if(!mark[next2]){
32 mark[next2]=true;
33 if(dfs(next2))return true;
34 p--;
35 }
36 return false;
37 }
38
39
40 int main(){
41 int _case,t=1,n,len;
42 scanf("%d",&_case);
43 while(_case--){
44 scanf("%d",&n);
45 getchar();
46 p=0;
47 memset(Text,0,sizeof(Text));
48 for(int page=1;page<=n;page++){
49 gets(str),len=strlen(str);
50 //
51 string s;
52 if(isalpha(str[len-1])){
53 for(int i=len-5;i<len;i++)s+=str[i];
54 char s1[MAXN];
55 if(s=="HAPPY"){
56 sscanf(str,"%*[^\"]\"%[^\"]\"%*[^ ]%*s",s1);
57 s=s1;
58 Text[page].str=s;
59 Text[page].tag=2;
60 }else {
61 sscanf(str,"%*[^\"]\"%[^\"]\"%*[^ ]%*s",s1);
62 s=s1;
63 Text[page].str=s;
64 Text[page].tag=1;
65 }
66 }else {
67 char s1[MAXN];
68 int x,y;
69 sscanf(str,"%*[^\"]\"%[^\"]\" %d %d",s1,&x,&y);
70 s=s1;
71 Text[page].str=s;
72 Text[page].tag=0;
73 C[page].f1=x,C[page].f2=y;
74 }
75 }
76 memset(mark,false,sizeof(mark));
77 mark[1]=true;
78 dfs(1);
79 printf("STORY %d
",t++);
80 for(int i=0;i<p;i++){
81 cout<<Text[path[i]].str<<endl;
82 }
83 }
84 return 0;
85 }
86
87
88
89
90