1038.cpp

zoj 的1038题。 典型的搜索问题。

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

 

char key[10][5] = {{""}, {""}, {"abc1"}, {"def1"}, 

                       {"ghi1"}, {"jkl1"}, {"mno1"}, 

                       {"pqrs"}, {"tuv1"}, {"wxyz"}}; 

 

typedef struct Dictionary

{

    char letter[105];

    int p;  

}Dictionary;

Dictionary word[1005];

char chr[105];

int WordNum;

 

typedef struct POSSIBLEWORD

{

    Dictionary w;

    int next;

}POSSIBLEWORD;

POSSIBLEWORD PossibleWord[1005];

char num[105];

 

int cmp(const void *a, const void *b)

{

    return strcmp((*(Dictionary *)a).letter, (*(Dictionary *)b).letter);

}

 

void InputDictionary()

{

    int i;

    scanf("%d", &WordNum);

    for(i = 0;i < WordNum;i++){

        scanf("%s%d", word[i].letter, &word[i].p);

    }

    qsort(word, WordNum, sizeof(word[0]), cmp);  

}

 

int find()

{

    int i, j, sum = 0, tag;

    for(i = 0;i < WordNum;i++){

        tag = 0;

         for(j = 0;chr[j];j++){

                if(chr[j] != word[i].letter[j]){

                    tag = 1;

                    break;

                }

        }

        if(tag == 0) sum += word[i].p;           

    }

    return sum;

}

 

void slove()

{

    int lnum, i, j, k, p, pp, s, t, maxp, tag, PossibleNum; 

    char tmp[105];

    PossibleWord[0].next = 1;  

    //建立链表  

    for(i = 0;i < WordNum;i++){

        strcpy(PossibleWord[i + 1].w.letter, word[i].letter);

        PossibleWord[i + 1].w.p = word[i].p;

        PossibleWord[i + 1].next = i + 2;      

    }

    PossibleWord[WordNum].next = -1;

    PossibleNum = WordNum;

    p = 0;

    lnum = strlen(num);

    i = 0;

    while(i < lnum){

        if(num[i] == '1') return;

        s = num[i] - '0';

        p = 0;

        maxp = -1;

        while(PossibleWord[p].next != -1){

            k = PossibleWord[PossibleWord[p].next].w.letter[i]; 

            tag = 0;         

            for(t = 0;t < 4;t++){

                if(k == key[s][t]){

                    tag = 1;

                    for(j = 0;j <= i;j++){

                        chr[j] = PossibleWord[PossibleWord[p].next].w.letter[j];

                    }

                    chr[j] = 0;

                    pp = find();

                    if(pp > maxp){

                        maxp = pp;

                        strcpy(tmp, PossibleWord[PossibleWord[p].next].w.letter);

                    }

                    break;  

                }

            }

            if(tag == 0){

                PossibleWord[p].next = PossibleWord[PossibleWord[p].next].next; 

                PossibleNum--;       

            }

            else p = PossibleWord[p].next;

        } 

        if(PossibleNum == 0){

            for(j = i;j < lnum - 1;j++){

                printf("MANUALLY\n");

            }

            return ;

        }

        for(j = 0;j <= i;j++){

            printf("%c", tmp[j]);

        }            

        printf("\n");

        i++;

    }

}

 

int main()

{

    //freopen("in.in", "r", stdin);

    //freopen("out.out", "w", stdout);

    int test, n,ca = 1;

    scanf("%d", &test);

    while(test--){

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

        InputDictionary();

        scanf("%d", &n);

        while(n--){

            scanf("%s", num);

            slove();

            printf("\n");

        }    

              printf("\n"); 

    }

    return 0;

}