stack+DFS ZOJ 1004 Anagrams by Stack

题目传送门

 /*
stack 容器的应用: 要求字典序升序输出,所以先搜索入栈的
然后逐个判断是否满足答案,若不满足,回溯继续搜索,输出所有符合的结果
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std; const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f; string s1, s2;
int len;
stack<char> S;
vector<char> V; void DFS(int push, int pop)
{
if (push == len && pop == len)
{
for (int i=; i<V.size (); ++i)
cout << V[i] << " ";
cout << endl;
} if (push + <= len) //入栈
{
S.push (s1[push]);
V.push_back ('i');
DFS (push+, pop);
S.pop ();
V.pop_back ();
} if (pop + <= push && pop + <= len && S.top () == s2[pop]) //出栈
{
char ch = S.top ();
S.pop ();
V.push_back ('o');
DFS (push, pop+);
S.push (ch);
V.pop_back ();
}
} int main(void) //ZOJ 1004 Anagrams by Stack
{
//freopen ("ZOJ_1004.in", "r", stdin); while (cin >> s1 >> s2)
{
V.clear ();
while (!S.empty ()) S.pop (); len = s1.length (); cout << "[" << endl;
DFS (, );
cout << "]" << endl;
} return ;
} /*
[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]
*/
上一篇:Xshell


下一篇:PDM使用问题总结