#include <iostream>#include <stdlib.h>#include <stdio.h>using namespace std;//定义页，存放输入的行数信息typedef struct{ int next1,next2; char type; string text; string end;}Page;Page page[101];//标记这个页数是否读过，0表示未读过，1表示已读过int mark[101];//存放路径，值0时表示到尾部int path[101];void init(){ for(int i = 0;i < 101; i++) { page[i].end = ""; page[i].text = ""; page[i].next1 = 0; page[i].next2 = 0; mark[i] = 0; path[i] = 0; }}//深度搜索，p表示下一页要读的页码索引，k表示路径长度，读到了第几页，每加一页k+1bool dfs(int p,int k){ //如果读过，就直接返回上级 if(mark[p]==1) return false; //记录路径，第k路径是第P页 path[k] = p; //标记这一页读过 mark[p] = 1; //读到故事结尾了，返回true if(page[p].type=='E'&&page[p].end.compare("HAPPY")==0) return true; if(page[p].type == 'C') { //此条路径成功返回true,因为每组数据只有一个结局，所以找到后即返回，不用再搜索了。 if(dfs(page[p].next1,k+1)) return true; if(dfs(page[p].next2,k+1)) return true; } //这条路径没有成功的完美故事结局，这条路径返回初始值，标记为未读，路径复位0 path[k] = 0; mark[p] = 0; return false;}//打印void print(){ int i = 1; while(path[i]!=0) { cout<<page[path[i]].text<<endl; i++; }}int main(){ int n; int x; int page1,page2; string text,end; string line; cin>>n; for(int m = 1; m <= n; m++) { cin>>x; getchar(); init(); for(int i = 1; i <= x; i++) { //一次读一行 getline(cin,line); //如果是C则按照C行格式初始化，先截取字符串，放在一个结构体中 if(line[0] == 'C') { page1 = atoi(line.substr(line.find_last_of(""")+2,1).c_str()); page2 = atoi(line.substr(line.find_last_of(""")+4,1).c_str()); text = line.substr(line.find_first_of(""")+1,line.find_last_of(""")-line.find_first_of(""")-1); page[i].next1 = page1; page[i].next2 = page2; page[i].text = text; page[i].type = 'C'; }else if(line[0] == 'E') { //如果是E则按照E行格式初始化，先截取字符串，放在一个结构体中 text = line.substr(line.find_first_of(""")+1,line.find_last_of(""")-line.find_first_of(""")-1); end = line.substr(line.find_last_of(""")+2,line.length()-line.find_last_of(""")); page[i].end = end; page[i].text = text; page[i].type = 'E'; } //把流和内容清空，注意,不然下次读完之后，内容有重复 line = ""; cin.clear(); } //从书的第一页开始搜索 mark[1] = 1; path[1] = 1; cout<<"STORY "<<m<<endl; if(dfs(page[1].next1,2)) print(); else { if(dfs(page[1].next2,2)) print(); } } return 0;}
