问题描述

给定多个“选择你的冒险”类型的故事结构，每个故事由若干页组成。每页可能是选择页（$C$）或结束页（$E$）。选择页包含两个选项，指向其他页；结束页标记为 $HAPPY$ 或 $GRISLY$。要求从第 $1$ 页出发，找到唯一一条通向 $HAPPY$ 结局的路径，并按顺序输出路径中所有页的文本内容。

解题思路

核心观察

1. 唯一路径：每个故事保证存在且仅存在一条通向 $HAPPY$ 结局的路径。
2. 反向推导：从 $HAPPY$ 页出发，反向遍历所有可能的前驱页面，直到找到起始页（第 $1$ 页）。

算法设计

1. 输入解析：
   • 解析每页的类型、文本、选项（$C$ 类型）或结局类型（$E$ 类型）。
   • 记录 $HAPPY$ 页的编号。
2. 反向 BFS 构建路径：
   • 从 $HAPPY$ 页开始，广度优先搜索（$BFS$）所有可能的前驱页面。
   • 维护 $prev$ 数组记录每个页面的前驱页，用于后续路径回溯。
3. 路径生成：
   • 从起始页（第 $1$ 页）出发，利用 $prev$ 数组回溯到 $HAPPY$ 页，生成完整路径。
4. 输出结果：
   • 按路径顺序输出每页的文本。

时间复杂度

1. 输入解析：$O(N \cdot L)$，其中 $L$ 为每行平均长度。
2. 反向 $BFS$：$O(N)$，每个页至多入队一次。
3. 路径生成与输出：$O(N)$。
   总时间复杂度为 $O(N)$，适用于 $N \leq 100$ 的约束。

代码实现

#include <iostream>
#include <stdio.h>
#include <map>
#include <string.h>
#include <algorithm>

const int maxn=110;
using namespace std;
int t,n;  
int endnum;  //以HAPPY结尾的页数
int pri[maxn];  //前驱
bool ok;  //标记是否已经找到路径
int vis[maxn];  //标记该页数是否被访问过

struct Page{
	int mark;
	char sentence[300];
	int len;
	int son[2];  //跳转的页码
	char ending[10]; 
	bool flag;  //flag为true表示该页是HAPPY
}page[maxn];

void dfs(int u){
	if(ok)
		return;
	vis[u]=1;  //没用vis标记前，RE；后来网上查了，有人说数据中有循环，便加上了标记，结果WA，忘记输出STORY X了。。。
	if(page[u].mark){
		for(int i=0;i<2;i++){
			int v=page[u].son[i];
			if(!vis[v]){
				pri[v]=u;
				dfs(v);
			}
		}
	}
	else{
		if(page[u].flag){
			ok=true;
			endnum=u;
		}
	}
}
int main()
{
	char s[3];
	char c;
	int len;
	cin>>t;
	for(int q=1;q<=t;q++){
		cout<<"STORY "<<q<<endl;
		memset(pri,-1,sizeof(pri));
		memset(vis,0,sizeof(vis));
		cin>>n;
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			page[i].mark=0;
			if(s[0]=='C'){
				page[i].mark=1;
				c=getchar();
				while(c!='"')
					c=getchar();
				len=0;
				//读取双引号里的句子
				while((c=getchar())!='"')
					page[i].sentence[len++]=c;
				page[i].len=len;
				scanf("%d%d",&page[i].son[0],&page[i].son[1]);
			}
			else{
				c=getchar();
				while(c!='"')
					c=getchar();
				len=0;
				//读取双引号里的句子
				while((c=getchar())!='"')
					page[i].sentence[len++]=c;
				page[i].len=len;
				
				scanf("%s",page[i].ending);
				if(strcmp(page[i].ending,"HAPPY")==0){
					page[i].flag=true;
				}
				else{
					page[i].flag=false;
				}
			}
		}
		pri[1]=1;
		ok=false;
		dfs(1);
		int idx=0;
		int res[maxn];
		res[idx++]=endnum;
		//存储路径
		while(pri[endnum]!=endnum){
			res[idx++]=pri[endnum];
			endnum=pri[endnum];
		}
		for(int i=idx-1;i>=0;i--){
			for(int j=0;j<page[res[i]].len;j++){
				cout<<page[res[i]].sentence[j];
			}
			cout<<endl;
		}
	}
	return 0;
}