hdu 1354

12914 ワード

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1354
考え方:最も面倒なのは文字列の処理ですが、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