字母转换
时限：1000ms 内存限制：10000K 总时限：3000ms
描述
通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成字符串1。输出结果需满足字典序。例如TROT 到 TORT:
[
i i i i o o o o
i o i i o o i o
]
[
i i i i o o o o
i o i i o o i o
]
输入
给定两个字符串，第一个字符串是源字符串，第二个字符是目标目标字符串。
输出
所有的进栈和出栈序列,输出结果需满足字典序
输入样例
madam adamm
bahama bahama
long short
eric rice
输出样例
[ 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 ]
提示：
采用回溯的方法
#include <iostream>
#include <string.h>
#include <stack>
using namespace std;
stack<char> minestack;
char data[25];
char plan[100];
char temp[100];
string aim;
string known;
bool TestPlan(int length)
{
//cout<<"Enter"<<endl;
int pos1 = 0,pos2 = 0;
for(int i = 0;i < length; i++)
if(plan[i]=='i')
{
minestack.push(known[pos1]);
pos1++;
}
else
{
if(!minestack.empty())
{
temp[pos2] = minestack.top();
minestack.pop();
pos2++;
}
else
return false;
}
for(int i = 0;i < length/2;i++)
if(temp[i]!=aim[i])
return false;
return true;
}
bool CountNum(int length)
{
//cout<<"hello"<<endl;
if(plan[0]=='o')
return false;
int count = 0;
for(int i = 0;i < length;i++)
if(plan[i]=='i')
count++;
if(count*2==length)
return true;
else
return false;
}
void FindPlan(int length,int pos)
{
if(pos==length)
{
if(CountNum(length))
{
if(TestPlan(length))
{
for(int i = 0;i < length;i++)
cout<<plan[i]<<" ";
cout<<endl;
}
}
}
else
{
plan[pos] = 'i';
FindPlan(length,pos+1);
plan[pos] = 'o';
FindPlan(length,pos+1);
}
}
int main()
{
cin>>known>>aim;
//stack<char> minestack;
//minestack.push(known[0]);
//cout<<minestack.top()<<endl;
int pos = 0;
FindPlan(2*known.length(),pos);
return 0;
}