P1019 单词接龙

清疚 2022-06-09 07:36 224阅读 0赞

P1019 单词接龙  
题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入输出格式

输入格式：  
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式：  
只需输出以此字母开头的最长的“龙”的长度

输入输出样例

输入样例\#1：  
5  
at  
touch  
cheat  
choose  
tact  
a  
输出样例\#1：  
23 （连成的“龙”为atoucheatactactouchoose）  
说明

NOIp2000提高组第三题

#### 这是一道dfs+字符串 ####

#### 接龙的规则是前后字符串有相同的部分（一开始以为是单个字符）。 ####

#### 而且每个串只能用两次。 ####

#### 因为只有二十个串，所以可以直接用搜索 ####

#### 再说字符串的连接的判断。 ####

#### 先取后一个字符串的第一个字符，在前者由后往前找一个相同的字符。然后两个指针分别判断由此到最后一个字符是否全部相同。 ####

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    
    using namespace std;
    int vis[21];
    int n;
    char dragon[21][256];
    int len[21];
    int maxs = 0;
    inline int read(){
           char c;
           int res,flag = 0;
           while((c = getchar())>'9'||c<'0')
                    if(c=='-')flag = 1;
           res = c - '0';
           while((c = getchar())>='0'&&c<='9')
           res =(res<<3)+(res<<1) + c - '0';
           return flag?-res:res;
    }
    inline int check(int a,int b){
        int i,k,j;  
        for(i=len[a]-1;i>=1;i--){   
            if(dragon[a][i]==dragon[b][0]){  
                int x=0;        
                for(k=i,j=0;k<len[a]&&j<len[b];k++,j++){  
                    if(dragon[a][k]==dragon[b][j])x++;  
                    else break;  
                }  
                if(k==len[a])return x;
            }  
        }  
        return 0;  
    }
    void dfs(int i,int lenx){
        bool flag =true;
        for (int j = 1;j<=n;j++){
            if(vis[j] < 2){
                    int t = check(i,j);
                    if(t!=0){
                        flag = false;
                        vis[j]++;
                        dfs(j,lenx+len[j]-t);
                        vis[j]--;
                    }
    
                }
            }
        if(flag == true){
            maxs = max(maxs,lenx);
        }
    }
    int main(){
         n = read(); 
        for (int i =1;i<=n;i++){
            cin>>dragon[i];
            len[i] = strlen(dragon[i]);
        }
        char c;
        cin>>c;
        memset(vis,0,sizeof(vis));
        for (int i = 1;i<=n;i++){
            if(dragon[i][0] == c){
                vis[i]+=1;
                dfs(i,len[i]);
                memset(vis,0,sizeof(vis));
            }
        }
        cout<<maxs;
    }