浙江大学ZOJ 1004题 详解
发布时间
阅读量：
阅读量
-
第一件事还是翻译题目，这道题目的意思大概是，有多组输入，每组输入有两行，第一行是一个单词（字符串）第二行是另外一个字符串（有可能组成字母都是相同的只不过是字母顺序不同，也有可能是另外的字符串，和原来的字符串没有多大关系），然后給你一个栈，你对这个栈和第一个字符串一共有两种操作，
-
第一种，压栈操作，执行这种操作会让第一个字符串的第一位放入栈中（就是说如果原来的字符串是madam，执行完一次压栈操作之后，原字符串就变成了adam，然后栈中就会有一个字母m。执行一次压栈操作需要输出一次i。
-
第二种，出栈操作，执行这种操作会让栈将栈顶元素弹出栈，放入一个字符串中，就是说如果栈中有，m，a两个元素，执行一次弹栈操作，接收的字符串会变成“m”，再弹一次会变成“ma”。执行一次出栈操作需要输出一次o。
-
题目问的是，第一个字符串需要经过上述两种操作变成第二个字符串（要把每一种方式都写出来），整个题目的输出格式大概为每组数据
[
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
]
四种不同方式的排序，为压栈操作平均越靠前，这组数据的排名越靠前（就是说处理的时候尽量先压栈就好了）。数据的每一行后面都是有空格的。如果第一个字符串不能成功变成第二个字符串就直接输出
[
]
就好了。 -
这道题也是一道用深度优先搜索就能成功A掉的题目，就是列出每一种分支选取正确分支输出就好了，有限查找压栈操作靠前的分支。而且第一行字符串如果能够成功变为第二行字符串的话，压栈出栈的操作数加起来应该是正好等于字符串长度的二倍，所以这就是递归搜索的退出条件。然后，
上代码
#include<iostream>
#include<string>
#include<stack>
using namespace std;
string a,b;//用来存每组字符串的第一个和第二个
int sum;//用来存每组需要的操作数目（等于第一组字符串长度的二倍）
//深度优先搜索函数，六个参数分别为，
//第一个字符串（初始字符串），第二个字符串（目标字符串），中间栈，
//出栈组成字符串，用来存放出入栈的字符数组，执行到当前的出入栈操作综合
void dfs(string a,string b,stack<char>temp,string now,char flag[100],int num)
{
//当出栈组成的字符串和目标字符串相同的时候，达到退出条件。
if(now==b)
{
for(int i=0;i<num;i++)
{
cout<<flag[i]<<" ";
}
cout<<endl;
return;
}
//减支，去掉不需要的数据
if(num>sum)
{
return;
}
string test;
string test_now=now;
char flag_test[100];
//判断能否压栈
if(a!="")
{
//压栈
temp.push(a[0]);
flag[num]='i';
test.assign(a,1,a.length()-1);
}
for(int j=0;j<=99;j++)
{
flag_test[j] = flag[j];
}
//压栈分支
if(a!="")
{
dfs(test,b,temp,test_now,flag_test,num+1);
if(!temp.empty())
temp.pop();
}
//出栈分支
if((!temp.empty())&&b[now.size()]==temp.top())
{
flag[num]='o';
string now_test = now+temp.top();
char testt = temp.top();
if(!temp.empty())
temp.pop();
dfs(a,b,temp,now_test,flag,num+1);
temp.push(testt);
}
}
int main()
{
while(cin>>a>>b)
{
string sumstring[10000]={""};
sum = 2*a.size()-1;//记录此组数据最大出入栈操作数总和
char flag[100];
string c="";
stack<char>temp;
cout<<"["<<endl;//规范输出格式
dfs(a,b,temp,c,flag,0);
cout<<"]"<<endl;
}
}
AI写代码- 结束
全部评论 (0)
还没有任何评论哟~