HDU 1298 T9 字典树+DFS

必须要批评下自己了，首先就是这个题目的迟疑不定，去年做字典树的时候就碰到这个题目了，当时没什么好的想法，就暂时搁置了，其实想法应该有很多，只是居然没想到。

同样都是对单词进行建树，并插入可能值，但是拨号键盘上的字母是对应多个的，给定拨号序列，有多种可能情况输出其中最可能的一种，肯定要想到搜索啊，而且拨号数目不超过100，每个按键最多只对应4个字母，复杂度并不高，所以用dfs是可行的，对于每次递归深度，dfs找到最大的可能值的情况并输出。

接下来就是要批评自己了，下午一点钟开始做这个题目，居然被一个小bug搞了一个多小时，都没过样例，就是我的dfs写挫了，而且我迟迟没找到原因。。。真的要反省自己的代码编写能力了。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int tot;

char s[];

char press[][];

char num[];

int ansd;

char anss[],finds[];

bool flag;

struct node

{

    node* ch[];

    int cur,deep;

} tree[];

node* newNode()

{

    node* p;

    p=&tree[tot++];

    for (int i=;i<;i++)

    {

        p->ch[i]=NULL;

    }

    p->cur=;

    p->deep=;

    return p;

}

void insertn(node* root,char* s1,int fee)

{

    node* p=root;

    int i=,k;

    //puts(s1);

    while (s1[i])

    {

        k=s1[i]-'a';

        if (p->ch[k]==NULL)

        {

            //cout<<s1[i]<<" "<<p->deep<<endl;

            p->ch[k]=newNode();

        }

        p->ch[k]->deep=i++;

        p->ch[k]->cur+=fee;

        p=p->ch[k];

    }

}

void init()

{

    strcpy(press[],"abc");

    strcpy(press[],"def");

    strcpy(press[],"ghi");

    strcpy(press[],"jkl");

    strcpy(press[],"mno");

    strcpy(press[],"pqrs");

    strcpy(press[],"tuv");

    strcpy(press[],"wxyz");

}

void dfs(node* rt,char* s1,int maxd,int d)

{

    node* p=rt;

    if (d==maxd)

    {

        if (p->cur>ansd){

            flag=;

            ansd=p->cur;

            for (int i=;i<d;i++)

                anss[i]=finds[i];

             anss[d]='\0';

            }

            return;

    }

    int k=s1[d]-'';

    for (int i=;press[k][i];i++)

    {

        int q=press[k][i]-'a';

        if (p->ch[q]!=NULL)

        {

            finds[d]=press[k][i];

        }

        else

            continue;

        dfs(p->ch[q],s1,maxd,d+);

    }

}

void test(node* root)

{

    node* p=root;

    for (int i=;i<;i++)

    {

        char c=i+'a';

        cout<<c<<" "<<i<<endl;

        if (p->ch[i]!=NULL) puts("Yes");

        else puts("NO");

        if (p->ch[i]!=NULL){

           // cout<<c<<" "<<p->deep<<endl;

          //  p=p->ch[i];

            //test(p);

        }

    }

}

int main()

{

    //freopen("d:\\hdu_1298.txt","w",stdout);

    int t,w,p,m,a,kase=;

    scanf("%d",&t);

    init();

    while (t--)

    {

        tot=;

        node* root=newNode();

        root->deep=-;

        scanf("%d",&w);

        for (int i=;i<w;i++)

        {

            scanf("%s %d",s,&p);

            //puts(s);

            //cout<<root->deep<<endl;

            //node*r1=root;

            //cout<<root->deep<<endl;

            insertn(root,s,p);

            //cout<<root->deep<<endl;

        }

        //test(root);

        scanf("%d",&m);

        printf("Scenario #%d:\n",++kase);

        for (int i=;i<m;i++)

        {

            scanf("%s",num);

            //puts(num);

            ansd=;

            flag=false;

            int len=strlen(num);

            for (int i=;i<len;i++)

            {

                ansd=;

                if (flag||i==){

                 flag=false;

                 dfs(root,num,i,);

                }

                if (flag)

                    puts(anss);

                else

                    puts("MANUALLY");

            }

            printf("\n");

        }

        printf("\n");

    }

    return ;

}

巴特西

HDU 1298 T9 字典树+DFS

最新文章

热门文章