首页 > 搜索 > DFS搜索 > hdu 2361 Bonus Word-DFS[解题报告]C++
2014
01-05

hdu 2361 Bonus Word-DFS[解题报告]C++

Bonus Word

问题描述 :

Lingo is a once popular game show where the contestants have to guess words. In the original version the contestants would have to guess a five-letter word each round.
In between the rounds of regular word guessing, the contestants can win a bonus prize if they can guess a ten-letter word. The ten-letter word is displayed with the letters permuted. Some letters are colored indicating that they are displayed in the right position. Since there are not that many ten-letter words, it happens frequently that the word is actually a compound: a word constructed by concatenating two shorter words. In this problem we
assume that the ten-letter word is always of this form.
Given a dictionary and a sequence of ten letters, you must calculate the possible solutions to the ten-letter word game. Two solutions are considered different if they are constructed from different parts, even if their concatenation is the same. This is illustrated by the the second sample case.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 200): the number of words in the dictionary.

n lines with a single word in the dictionary. Each word is between 1 and 9 (inclusive) characters long and consists of only lowercase letters.

One line with an integer q (1 <= q <= 100): the number of queries.

q lines with a single query string. Each query is exactly 10 characters long and will consist of uppercase and lowercase letters. Lowercase letters are in the right position and uppercase letters may be in the wrong position.
All words in the dictionary for a single test case are distinct.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 200): the number of words in the dictionary.

n lines with a single word in the dictionary. Each word is between 1 and 9 (inclusive) characters long and consists of only lowercase letters.

One line with an integer q (1 <= q <= 100): the number of queries.

q lines with a single query string. Each query is exactly 10 characters long and will consist of uppercase and lowercase letters. Lowercase letters are in the right position and uppercase letters may be in the wrong position.
All words in the dictionary for a single test case are distinct.

样例输入:

2
5
gunner
integral
relating
tail
un
4
TAILGUNNER
unINTEGRAL
UNrelating
IMPOSSIBLE
3
aaaa
aaaaa
aaaaaa
1
AAAAAAAAAA

样例输出:

6
gunner-tail
integral-un
relating-un
tail-gunner
un-integral
un-relating
2
un-integral
un-relating
1
un-relating
0
3
aaaa-aaaaaa
aaaaa-aaaaa
aaaaaa-aaaa


对于这个题目让我十分的失望!找了半天的错误原来是DFS时,对于一种情况的hash没有弄。
这个题目是字典树的应用,也可以用二分做!
我是用字典树做的,加上自己模板改了下,原本以为一下就过,没想到! 唉!
贴DFS的内容,以后不再犯:

void FindStr(DicTree &DicT,DicTree &Root,char strs[], int p, int hash[], bool flag) //true for second, false for first
{ 
    int i;
    if(flag==true&&p==10) 
    {
        if(DicT->tail==true)
        {
            if(lens<1000)
            {
            outstr[p+1]='\0'; 
            strcpy(outs[lens],outstr); 
            } 
            lens++;
        }
        return ;
    }
    if(strs[p]>='a'&&strs[p]<='z')
    {
        if(DicT->letter[strs[p]-'a']!=NULL)
        {   
            if(flag==false&&DicT->letter[strs[p]-'a']->tail==true)
            {
                outstr[p]=strs[p];
                outstr[p+1]='-';
                FindStr(Root,Root,strs,p+1,hash,true);
            }
            outstr[p+(flag==true)]=strs[p];
            FindStr(DicT->letter[strs[p]-'a'],Root,strs,p+1,hash,flag); 
        }
    }
    else
    {
        for(i=0;i<26;i++)
            if(hash[i]!=0&&DicT->letter[i]!=NULL)
            {
                hash[i]--;    
                if(flag==false&&DicT->letter[i]->tail==true)
                 {
                     outstr[p]=i+'a';
                     outstr[p+1]='-';
                     FindStr(Root,Root,strs,p+1,hash,true);
                 }
                //hash[i]--;//错误之处
                outstr[p+(flag==true)]=i+'a';
                FindStr(DicT->letter[i],Root,strs,p+1,hash,flag);
                hash[i]++;
            }
    }
    
}

转自:http://hi.baidu.com/dellenge/item/836244ebcf17e7226cabb84e


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.