Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 18095 Accepted
Submission(s): 6764
1 #include <iostream>
2 #include <stack>
3 using namespace std;
4 char o1[1001],o2[1001];
5 bool q[1001];
6 int n;
7 bool dfs(bool c,int cn,int index1,int index2,stack <char> s)
8 {
9 if(cn>=2*n)
10 return true;
11 if(c==true){ //当前要求入栈
12 if(index1>=n)
13 return false;
14 s.push(o1[index1++]);
15 q[cn] = c;
16 }
17 else {
18 if(s.empty())
19 return false; //当前这样操作不可以
20 else{
21 char t;
22 if(s.top()==o2[index2]){
23 index2++;
24 s.pop();
25 q[cn] = c;
26 }
27 else
28 return false;
29 }
30 }
31 if(dfs(true,cn+1,index1,index2,s))
32 return true;
33 else if(dfs(false,cn+1,index1,index2,s))
34 return true;
35 return false;
36 }
37 int main()
38 {
39 while(cin>>n){
40 cin>>o1>>o2;
41 //true为入栈,false为出栈
42 stack <char> s;
43 if(dfs(true,0,0,0,s)){ //返回情况
44 cout<<"Yes."<<endl;
45 for(int i=0;i<n*2;i++)
46 if(q[i])
47 cout<<"in"<<endl;
48 else
49 cout<<"out"<<endl;
50 cout<<"FINISH"<<endl;
51 }
52 else{
53 cout<<"No."<<endl;
54 cout<<"FINISH"<<endl;
55 }
56 }
57 return 0;
58 }
Freecode : www.cnblogs.com/yym2013
hdu 1022:Train Problem I(数据结构,栈,递归,dfs)
原文:http://www.cnblogs.com/yym2013/p/3550155.html