Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1004K-AnagramsByStack-Zju
发信站: 哈工大紫丁香 (2002年10月06日19:57:45 星期天), 站内信件

这个题目没什么特别的，回溯加上简单的剪枝

#include"stdio.h"
#include"iostream.h"
#include"string.h"
#include"stack"
#include"queue"
using namespace std;
int t=0;
stack<char> ss;
int go(char* qq,int pq,char* src,int ps,char* dest,int pd)
{
    int i;
    char c;
    if(pd>ps||ps>strlen(src)) return 0;
    if(pq==2*strlen(src))
    {
        int k=0,p=0,q=0;
        for(i=0;i<2*strlen(src);i++)
        {
            if(qq[i]=='i')
            {
                ss.push(src[p++]);
            }
            else
            {
                c=ss.top();
                if(dest[q++]!=c)
                    return 0;
                ss.pop();
            }
        }
        for(i=0;i<2*strlen(src);i++)
            printf("%c ",qq[i]);
        printf("\n");
        return 0;
    }
    qq[pq]='i';
    go(qq,pq+1,src,ps+1,dest,pd);
    qq[pq]='o';
    go(qq,pq+1,src,ps,dest,pd+1);
    return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("anagrams.in","r",stdin);
#endif
    char src[100],dest[100],qq[100];
    char test[100];
    memset(test,0,100);
    int pos=0;
    memset(qq,0,100);
    while(gets(src),gets(dest))
    {
        printf("[\n");
        go(qq,0,src,0,dest,pos);
        printf("]\n");
    }
    return 0;
}
--
５、在快餐店送汉堡包并不是作践自己，你的祖父母对此

有另外的理解：机会。

                                    ——比尔·盖茨

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.231]