首页 > ACM题库 > HDU-杭电 > HDU 1354 Choose Your Own Adventure-DFS-[解题报告] C++
2013
12-09

HDU 1354 Choose Your Own Adventure-DFS-[解题报告] C++

Choose Your Own Adventure

问题描述 :

After reading the book Tim and Marc Kill Kenny about fifty zillion times, James decided he’d had it with choose-your-own-adventure stories. No matter what choices he made, it seemed like Kenny always fell down an abandoned mine shaft, got run over by a bus load of nuns, or was messily devoured by stray cats. James eventually found the page with the happy ending (where Kenny saves himself by trapping Tim and Marc between the pizza and the hungry programmers) by flipping through the book, but he can’t figure out how to get there by following the rules. Luckily, he owns a C compiler…

输入:

Input to this problem will consist of a (non-empty) series of up to 100 data sets, each representing a choose-your-own-adventure story. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

The first line contains a single integer n indicating the number of data sets.

A single data set has 2 components:

1. Page Count – A line containing a single integer X, where 1 < X < 100, indicating the number of pages in the story.
2. Page List – A sequence of X lines, each of which represents a page from the book. Each line has the following components separated from one another by single spaces:

  • Line type – A single character indicating what type of line this is. It will represent either a "C" choice page, or an "E" end page. Page 1 is always a choice page.
  • Text – A string of text surrounded by double quotes. Including the quotes, this component will not exceed 256 characters. The quotes are given for input purposes only and should not be considered part of the text. The text will not contain embedded double quotes.
  • Choices – Two positive integers from 1 to X indicating the pages where the reader can go from this page. Only choice pages have this component.
  • Ending Type – Either the text "HAPPY" or "GRISLY". There will only be one happy ending per story, and only end pages have this component.

输出:

For each story in the input:

  • Output a single line, "STORY #" where # is 1 for the first story, 2 for the second story, etc.
  • Determine the story that begins on page 1 and ends on the happy ending page. Output the text of this story, printing one "page" of text per line. Note that there is only one such story for each data set.

样例输入:

2
3
C "Arrived at LSU for the contest" 2 3
E "Was devoured by sidewalk ants" GRISLY
E "Won the contest. Received glory and nachos." HAPPY
5
C "Saw a peanut" 3 5
E "Made peanut butter sandwich" HAPPY
C "Found a hammer" 4 2
E "Hit self on head with hammer, ouch!" GRISLY
E "Ate the peanut, choked on it, and died" GRISLY

样例输出:

STORY 1
Arrived at LSU for the contest
Won the contest. Received glory and nachos.
STORY 2
Saw a peanut
Found a hammer
Made peanut butter sandwich

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1354

思路:最麻烦的就是字符串处理了,但sscanf函数功能相当强大,orz….然后dfs就可以了,但才过了18个人。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<string>
 using namespace std;
 #define MAXN 333
 struct Node{
     int f1,f2;
 }C[MAXN];
 char str[MAXN];
 int path[MAXN];
 bool mark[MAXN];
 int p;
 struct Page{
     int tag;
     string str;
 }Text[MAXN];
 
 bool dfs(int page){
     path[p++]=page;
     if(Text[page].tag==2)return true;
     if(Text[page].tag==1)return false;
     int next1=C[page].f1;
     int next2=C[page].f2;
     if(!mark[next1]){
         mark[next1]=true;
         if(dfs(next1))return true;
         p--;
     }
     if(!mark[next2]){
         mark[next2]=true;
         if(dfs(next2))return true;
         p--;
     }
     return false;
 }
 
 
 int main(){
     int _case,t=1,n,len;
     scanf("%d",&_case);
     while(_case--){
         scanf("%d",&n);
         getchar();
         p=0;
         memset(Text,0,sizeof(Text));
         for(int page=1;page<=n;page++){
             gets(str),len=strlen(str);
             //是字母
             string s;
             if(isalpha(str[len-1])){
                 for(int i=len-5;i<len;i++)s+=str[i];
                 char s1[MAXN];
                 if(s=="HAPPY"){
                     sscanf(str,"%*[^\"]\"%[^\"]\"%*[^ ]%*s",s1);
                     s=s1;
                     Text[page].str=s;
                     Text[page].tag=2;
                 }else {
                     sscanf(str,"%*[^\"]\"%[^\"]\"%*[^ ]%*s",s1);
                     s=s1;
                     Text[page].str=s;
                     Text[page].tag=1;
                 }
             }else {
                 char s1[MAXN];
                 int x,y;
                 sscanf(str,"%*[^\"]\"%[^\"]\" %d %d",s1,&x,&y);
                 s=s1;
                 Text[page].str=s;
                 Text[page].tag=0;
                 C[page].f1=x,C[page].f2=y;
             }
         }
         memset(mark,false,sizeof(mark));
         mark[1]=true;
         dfs(1);
         printf("STORY %d\n",t++);
         for(int i=0;i<p;i++){
             cout<<Text[path[i]].str<<endl;
         }
     }
     return 0;
 }

 

解题报告转自:http://www.cnblogs.com/wally/archive/2013/05/06/3063675.html


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。