［水］ZOJ1004

給原始串和目标串

問怎麼通過棧把原始串變成目标串

DFS一下每種操作【先搜入棧/後搜彈出】然後判斷輸出就好

坑在...每一種方案最後需要有個空格= =然後再換行，坑了一次PE

#include <bits/stdc++.h>

using namespace std;
char s1[100],s2[100];
int a[100],b[100];
int l1,l2;
int tem[100],ans[100];
stack<int> stk;
void Ok()
{
    int flag=1;
    if (l1!=l2)
        return ;
    for (int i=1; i<=l1; i++)
        if (b[i-1]!=ans[i])
        {
            flag=0;
            break;
        }
    if (flag==1)
    {
        for (int i=1; i<=2*l1; i++)
        {
            if (tem[i]==1)
                cout<<"i ";
            else
                cout<<"o ";
        }
        cout<<endl;
    }
    return ;
}
void dfs(int nn,int opt,int l)
{
    //cout<<opt<<" ";
    if(opt==2*l1)
    {
        if (l!=l1) return;
        Ok();
        return ;
    }
    if (nn!=l1) //push
    {
        stk.push(a[nn]);
        tem[opt+1]=1;
        dfs(nn+1,opt+1,l);
        stk.pop();
    }
    if (!stk.empty())//pop
    {
        int t=stk.top();
        stk.pop();
        tem[opt+1]=2;
        ans[l+1]=t;
        dfs(nn,opt+1,l+1);
        stk.push(t);
    }
    return ;
}
void Gao()
{
    memset(ans,0,sizeof(ans));
    memset(tem,0,sizeof(tem));
    while (!stk.empty())stk.pop();
    l1=strlen(s1);
    l2=strlen(s2);
    if (l1!=l2)
        return ;
    for (int i=0; i<l1; i++)
        a[i]=s1[i]-'a'+1;
    for (int i=0; i<l2; i++)
        b[i]=s2[i]-'a'+1;
    dfs(0,0,0);
    return ;
}
int main()
{
    freopen("a.in","r",stdin);
    while (scanf("%s",s1)!=EOF)
    {
        scanf("%s",s2);
        cout<<"["<<endl;
        Gao();
        cout<<"]"<<endl;
    }
    return 0;
}