poj 2023 Choose Your Own Adventure (데이터 구조 + 심층 검색)
17330 단어 데이터 구조
Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 1559
Accepted: 638
Description
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
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:
Output
For each story in the input:
Sample Input
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
Sample Output
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
:
(1) ,
(2) , ,
(4) , C , , ,E
(5) happy , , happy
Source
#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+1
bool 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.