シミュレーションスタックの遡及,完全二叉木探索,(ZOJ 1004)

タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1004
問題解決レポート:
①方法:完全二叉木の探索方式、遡及法.
②コード解釈:
1、ずっとスタックに入ることができて、スタックに入ることができない时、スタックを出るしかありません.
2、先にスタックに入ってから、スタックを出ます.スタックが空にならないようにします.
3、dfs(i,j)が完了した後(i>1)、スタックアウト操作が可能になった場合、dfs(i,j+1)を行い、答えに近づく.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

string a,b;///        ;

stack <char> build;///       
vector <char> operate;///       
int len;///   a  


///iPush         ，iPop         ；
void dfs(int iPush,int iPop)
{
    ///                   ，        。
    if(iPush==len&&iPop==len)
    {
        for(int i=0;i<operate.size();i++)
            cout<<operate[i]<<" ";
        cout<<endl;
    }
    ///    ；
    if(iPush+1<=len)
    {
        build.push(a[iPush]);
        operate.push_back('i');
        dfs(iPush+1,iPop);
        build.pop();
        operate.pop_back();
    }
    ///    ；
    if(iPop+1<=iPush&&iPop+1<=len&&build.top()==b[iPop])
    {
        char tc=build.top();
        build.pop();
        operate.push_back('o');
        dfs(iPush,iPop+1);
        build.push(tc);
        operate.pop_back();
    }
}


int main()
{
    while(cin>>a>>b)
    {
        len=a.length();
        cout<<"["<<endl;
        dfs(0,0);
        cout<<"]"<<endl;
    }
    return 0;
}