sgu179 SGU起航！

//发现dfs除了搜索功能外的其他功能，他本身是一种序列，这个题恰是“先序”的下一个（合法范围内）序列！

#include<iostream>

#include<string>

#include<vector>

using namespace std;

struct state

{

    string s;

    int sum_0;

    int sum_1;

};

vector<state>v;

bool flag;

void dfs(int cur,state ss,int size,string xulie)

{

    if(cur%2==0)  //剪枝一：一旦发现小了，马上回溯！

    {

        string temp1(xulie,0,cur-1);//只比前cur个字符

       if(ss.s<temp1)

        {

          return;

        }

    }

    if(flag==1)return;

    if(cur==size)   //一次获得即可返回，DFS序列本可以是字典序！

    {

        if(ss.sum_0==ss.sum_1&&ss.s>xulie)

           { v.push_back(ss);flag=1;}

    }

    else

    {

        if(ss.sum_0<=size/2)

        {

              state temp_ss(ss);      //只建立临时对象传递下去！

              temp_ss.sum_0=ss.sum_0+1;temp_ss.s=ss.s+"0";

              dfs(cur+1,temp_ss,size,xulie);

        }

        if(ss.sum_1+1<=ss.sum_0)

        {

             state temp_ss(ss);

             temp_ss.sum_1=ss.sum_1+1;temp_ss.s=ss.s+"1";

              dfs(cur+1,temp_ss,size,xulie);

        }

    }

}

int main()

{    string xulie;

    while(cin>>xulie)

    {

        v.clear();

        flag=0;

        state ss;

      ss.s="0";ss.sum_0=1;ss.sum_1=0;

     for(int i=0;i<xulie.size();i++)

      {

          if(xulie[i]=='(')

               xulie[i]='0';

          else

             xulie[i]='1';

      }

      dfs(1,ss,xulie.size(),xulie);

          if(!v.empty())

           {

               string temp2;

               for(int i=0;i<v[0].s.size();i++)

                    {

                        if((v[0].s)[i]=='0')

                         temp2+='(';

                        else

                        temp2+=')';

                    }

                cout<<temp2<<endl;

           }

          else cout<<"No solution"<<endl;

    }

}
巴特西

sgu179 SGU起航！

最新文章

热门文章
