Coder Space

PKU 2023 Choose Your Own Adventure --- BFS

简单的BFS，不过要注意输入，getline(cin,str,'/"')函数运用。

  1/*
  2   Problem: 2023  User: Uriel 
  3   Memory: 200K  Time: 0MS 
  4   Language: C++  Result: Accepted 
  5*/
  6
  7/*
  8   简单BFS，注意输入，getline函数
  9*/
 10
 11#include<iostream>
 12#include<string>
 13#include<queue>
 14
 15using namespace std;
 16
 17struct Node
 18{
 19    int page;
 20    int prePage;
 21    char lineType;
 22    string text;
 23    int choice[2];
 24    string endingType;
 25};
 26
 27Node s[100];
 28
 29void Process()
 30{
 31    int i;
 32    Node cur;
 33    int res[100],k;
 34
 35    queue<Node> q;
 36    q.push(s[1]);
 37    s[1].prePage=0;
 38    while(!q.empty())
 39    {
 40        cur=q.front();
 41        q.pop();
 42        if(cur.lineType=='C')
 43        {
 44            s[cur.choice[0]].prePage=cur.page;
 45            s[cur.choice[1]].prePage=cur.page;
 46            q.push(s[cur.choice[0]]);
 47            q.push(s[cur.choice[1]]);
 48        }
 49        else        //cur.lineType='E'
 50        {
 51            if(cur.endingType=="HAPPY")
 52            {
 53                k=1;
 54                i=cur.prePage;
 55                while(i!=1)
 56                {
 57                    res[k++]=i;
 58                    i=s[i].prePage;
 59                }
 60                res[k]=1;
 61
 62                while(k>0)
 63                {
 64                    cout<<s[res[k--]].text<<endl;
 65                }
 66                cout<<cur.text<<endl;
 67                return;
 68            }
 69            else                 //cur.endingType=="GRISLY"
 70            {
 71                //do nothing
 72            }
 73        }
 74    }
 75}
 76
 77int main()
 78{
 79    int n,X;
 80
 81    int i,j;
 82    char c;
 83
 84    cin>>n;
 85    for(j=1;j<=n;j++)
 86    {
 87        cin>>X;
 88        for(i=1;i<=X;i++)
 89        {
 90            s[i].page=i;
 91            cin>>s[i].lineType;
 92            cin>>c;
 93            getline(cin,s[i].text,'\"');
 94            if(s[i].lineType=='C')
 95            {
 96                cin>>s[i].choice[0]>>s[i].choice[1];
 97            }
 98            else
 99            {
100                cin>>s[i].endingType;
101            }
102        }
103        cout<<"STORY "<<j<<endl;
104
105        Process();
106    }
107    return 0;
108}

posted on 2010-04-29 21:34 David Liu 阅读(125) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论