DFS+剪枝.剪枝主要是判断现有输出是否与最终期望字符串前缀匹配.
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
Code
1
#include <iostream>
2
#include <string>
3
#include <vector>
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
enum Operand
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
INPUT,
9
OUTPUT
10
};
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
string input, output;
13
vector<vector<char> > final_result;
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
// To see if input and output are stackable, simply compare the length
16
bool IsPossibleStackable(string input, string output)
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
18
if(input.length() != output.length())
19
return false;
20
return true;
21
}
22![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
23
// To see v is equal to string s
24
bool IsEqual(vector<char> & v, string s)
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
34
// If the element in v doesn't belong to the front char in s, it will never match the whole string
35
bool IsOutPossible(vector<char> & v, string s)
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
37
for(int i = 0; i < v.size(); ++i)
38![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
39
if(v[i] != s.at(i))
40
return false;
41
}
42
return true;
43
}
44![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
45
void DFS_Help(vector<char> in_stack, vector<char> out_stack, vector<char> result, int position, Operand op)
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
47
// Come to the actually action
48
// INPUT action:
49
if(op == INPUT)
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
57
// OUTPUT action:
58
if(op == OUTPUT)
59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
68
// Congratulations! We found the result.
69
if(IsEqual(out_stack, output))
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
// Store my hard-work :)
72
final_result.push_back(result);
73
return;
74
}
75![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
80
// Can we INPUT?
81
if(position < input.length())
82
DFS_Help(in_stack, out_stack, result, position, INPUT);
83![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
84
// Can we OUTPUT?
85
if(in_stack.size() != 0)
86
DFS_Help(in_stack, out_stack, result, position, OUTPUT);
87
}
88
}
89![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
90
void DFS()
91![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
92
vector<char> in, out, result;
93
DFS_Help(in, out, result, 0, INPUT);
94
}
95![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
96
int _tmain(int argc, _TCHAR* argv[])
97![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
98
bool isfound = true;
99
while(cin >> input >> output)
100![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
101
if(IsPossibleStackable(input, output))
102![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
103
DFS();
104
}
105
int size = final_result.size();
106![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
107
cout << "[" << endl;
108![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
109
for(int i = 0; i < size; ++i)
110![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
111
int inner_size = final_result.at(i).size();
112
for(int j = 0; j < inner_size; ++j)
113![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
114
cout << final_result.at(i).at(j) << " ";
115
}
116
cout << endl;
117
}
118![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
119
cout << "]" << endl;
120![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
121
final_result.clear();
122
}
123
return 0;
124
}
125![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
126![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2009-03-24 20:45
肖羽思 阅读(1888)
评论(2) 编辑 收藏 引用 所属分类:
ZOJ