stack+DFS ZOJ 1004 Anagrams by Stack

 1 /*
 2     stack 容器的应用：    要求字典序升序输出，所以先搜索入栈的
 3         然后逐个判断是否满足答案，若不满足，回溯继续搜索，输出所有符合的结果
 4 */
 5 #include <cstdio>
 6 #include <iostream>
 7 #include <algorithm>
 8 #include <stack>
 9 #include <cmath>
10 #include <cstring>
11 #include <vector>
12 using namespace std;
13 
14 const int MAXN = 1e4 + 10;
15 const int INF = 0x3f3f3f3f;
16 
17 string s1, s2;
18 int len;
19 stack<char> S;
20 vector<char> V;
21 
22 void DFS(int push, int pop)
23 {
24     if (push == len && pop == len)
25     {
26         for (int i=0; i<V.size (); ++i)
27             cout << V[i] << " ";
28         cout << endl;
29     }
30 
31     if (push + 1 <= len)        //入栈
32     {
33         S.push (s1[push]);
34         V.push_back (‘i‘);
35         DFS (push+1, pop);
36         S.pop ();
37         V.pop_back ();
38     }
39 
40     if (pop + 1 <= push && pop + 1 <= len && S.top () == s2[pop])        //出栈
41     {
42         char ch = S.top ();
43         S.pop ();
44         V.push_back (‘o‘);
45         DFS (push, pop+1);
46         S.push (ch);
47         V.pop_back ();
48     }
49 }
50 
51 int main(void)        //ZOJ 1004 Anagrams by Stack
52 {
53     //freopen ("ZOJ_1004.in", "r", stdin);
54 
55     while (cin >> s1 >> s2)
56     {
57         V.clear ();
58         while (!S.empty ())    S.pop ();
59 
60         len = s1.length ();
61 
62         cout << "[" << endl;
63         DFS (0, 0);
64         cout << "]" << endl;
65     }
66 
67     return 0;
68 }
69 
70 /*
71 [
72 i i i i o o o i o o 
73 i i i i o o o o i o 
74 i i o i o i o i o o 
75 i i o i o i o o i o 
76 ]
77 [
78 i o i i i o o i i o o o 
79 i o i i i o o o i o i o 
80 i o i o i o i i i o o o 
81 i o i o i o i o i o i o 
82 ]
83 [
84 ]
85 [
86 i i o i o i o o 
87 ]
88 */