DFS+剪枝.剪枝主要是判斷現有輸出是否與最終期望字符串前綴匹配.
Code
1
#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6enum Operand
7
{
8
INPUT,
9 OUTPUT
10
};
11
12string input, output;
13vector<vector<char> > final_result;
14
15// To see if input and output are stackable, simply compare the length
16bool IsPossibleStackable(string input, string output)
17{
18 if(input.length() != output.length())
19 return false;
20 return true;
21}
22
23// To see v is equal to string s
24bool IsEqual(vector<char> & v, string s)
25{
26 if(v.size() != s.length())
27 return false;
28 string temp;
29 for(size_t i = 0; i < v.size(); ++i)
30 temp += v[i];
31 return strcmp(s.c_str(), temp.c_str()) == 0;
32}
33
34// If the element in v doesn't belong to the front char in s, it will never match the whole string
35bool IsOutPossible(vector<char> & v, string s)
36{
37 for(int i = 0; i < v.size(); ++i)
38
{
39 if(v[i] != s.at(i))
40 return false;
41
}
42 return true;
43}
44
45void DFS_Help(vector<char> in_stack, vector<char> out_stack, vector<char> result, int position, Operand op)
46{
47 // Come to the actually action
48 // INPUT action:
49 if(op == INPUT)
50 {
51 // push element into stack, and increase the position(for the next push, it will be the next element)
52 in_stack.push_back(input.at(position++));
53 // store my work
54 result.push_back('i');
55 }
56
57 // OUTPUT action:
58 if(op == OUTPUT)
59 {
60 // store it in out_stack
61 out_stack.push_back(in_stack[in_stack.size() - 1]);
62 // pop it from in_stack
63 in_stack.pop_back();
64 // store my work
65 result.push_back('o');
66 }
67
68 // Congratulations! We found the result.
69 if(IsEqual(out_stack, output))
70 {
71 // Store my hard-work :)
72 final_result.push_back(result);
73 return;
74 }
75
76 // now let's search next
77 // Put INPUT before OUTPUT because I is smaller than O as sequences should be in "dictionary order"
78 if(IsOutPossible(out_stack, output))
79 {
80 // Can we INPUT?
81 if(position < input.length())
82 DFS_Help(in_stack, out_stack, result, position, INPUT);
83
84 // Can we OUTPUT?
85 if(in_stack.size() != 0)
86 DFS_Help(in_stack, out_stack, result, position, OUTPUT);
87 }
88}
89
90void DFS()
91{
92 vector<char> in, out, result;
93 DFS_Help(in, out, result, 0, INPUT);
94}
95
96int _tmain(int argc, _TCHAR* argv[])
97{
98 bool isfound = true;
99 while(cin >> input >> output)
100 {
101 if(IsPossibleStackable(input, output))
102 {
103 DFS();
104 }
105 int size = final_result.size();
106
107 cout << "[" << endl;
108
109 for(int i = 0; i < size; ++i)
110 {
111 int inner_size = final_result.at(i).size();
112 for(int j = 0; j < inner_size; ++j)
113 {
114 cout << final_result.at(i).at(j) << " ";
115 }
116 cout << endl;
117 }
118
119 cout << "]" << endl;
120
121 final_result.clear();
122 }
123 return 0;
124}
125
126posted on 2009-03-24 20:45
肖羽思 閱讀(1939)
評論(2) 編輯 收藏 引用 所屬分類:
ZOJ