ZOJ 1004 Anagrams by Stack

于 2011年02月3日 发布在 算法&&ACM 跳到评论

ZOJ 1004 Anagrams by Stack

这个题很早就看到了,但是当时关于栈没有很好的运用,而且还需要用递归所以就放过了。。今天重拾这个题,感觉应付起来很轻松,可能是因为进步了吧,嘿嘿。。1A~

i代表入栈操作,o代表弹出,对于一个字符串,从第一个字符开始,进行一系列的栈操作,问有没有可能出栈的字符可以按顺序组成另外一个字符串。ok函数表示得到的io操作是否能得到另外一个串。

#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>

using namespace std;
string START,END;
int CountI,CountO;
char IO[500];
int ok(void)
{
    stack<char> S;
    string result;
    int i,in = 0;
    for( i = 0; i < 2*END.length(); i++ )
    {
        if( IO[i] == 'i' )
            S.push(START[in++]);
        else
            result.append( 1,S.top() ),S.pop();
    }
    if( END == result ) return 1;
    else return 0;
}
void GeneIO( int x ,int CountI,int CountO )
{
    int i;
    if( x == 2*END.length() )
    {
        if( CountI - CountO ) return;
        if( ok() )
        {
            for( i = 0; i < 2*END.length(); i++ )
                cout << IO[i] << ' ';
            cout << endl;
        }
        return;
    }
    if( CountI > CountO )
    {
        IO[x] = 'i';
        GeneIO( x + 1 ,CountI + 1,CountO );
        IO[x] = 'o';
        GeneIO( x + 1 ,CountI,CountO + 1 );
    }
    else if( CountI == CountO )
    {
        IO[x] = 'i';
        GeneIO( x + 1 ,CountI + 1,CountO );
    }
}

int main(void)
{
    
    while( cin >> START >> END )
    {
        if( START.length() != END.length() )
        {
            cout << '[' << endl << ']' << endl;
            continue;
        }
        cout << '[' << endl;
        GeneIO(0,0,0);
        cout << ']' << endl;
    }    
    return 0;
}

本文共有 一条评论 | 沙发:文章评论

  1. ZXY说道:

    有网真好,呜呜…

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)