单词接龙(dragon)（BFS）

单词接龙(dragon)

时间限制: 1 Sec 内存限制: 64 MB
提交: 12 解决: 5
[提交][状态][讨论版]

题目描述

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

输入

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

输出

输出以此字母开头的最长的“龙”的长度。

样例输入

5

at

touch

cheat

choose

tact

a

样例输出

提示

样例说明：连成的“龙”为atoucheatactactouchoose。

【分析】哎这个题一开始WA了好几发仔细检查发现好多BUG 主要是判断两个字符串相交部分想错了题目要求最长龙而我找重复子字符串时是从

首字符串头部开始遍历找的导致在有些情况下把重复字符串找长了例如：（头）CDABABA （尾）BABABA 这个时候重复字符串应该是BA 而不应该

是BABA 哎还是我太菜路还长需要学的还很多下面是AC代码可能还可以优化谁让我太菜 wo te e fa ke?

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

#define inf 0x3f3f3f3f

#define mod 1000000007

typedef long long ll;

using namespace std;

const int N=;

int n,dp[N],len;

int w[][];

int g[];

int b,c;

string str[],ch;

int maxn=;

map<string,int>p,pp;

struct man

{

    string sa;

    int aa[];

};

int charge(string a,string b)

{

    for(int ii=a.size()-;ii>=;ii--)

    {

        int jj=ii,kk=;

        while(jj<a.size()&&kk<b.size())

        {

            if(a[jj]!=b[kk])break;

            jj++;kk++;

        }

        if(jj==a.size()&&ii!=)return (kk);

        else if(jj==a.size()&&ii==) return ;

        else if(jj==a.size()&&kk==b.size())return ;

    }

}

void bfs()

{

    queue<man>q;

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

    {

        if(str[i][]==ch[])

        {

            man CH;

             CH.sa=str[i];

            for(int j=;j<=;j++){CH.aa[j]=;if(i==j)CH.aa[i]=;}

            q.push(CH);

        }

    }

    while(!q.empty())

    {

        man t=q.front();

        int y=t.sa.size();

        maxn=max(maxn,y);

        q.pop();

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

        {

            string l=str[i],k;

            if(t.aa[i]>=)continue;

            int mm=charge(t.sa,l);

            //printf("!!!%d\n",mm);

            if(mm==)continue;

            else

            {

                man K=t;

             K.aa[i]++;

               l= l.erase(,mm);

                k=t.sa+l;

                K.sa=k;

                if(pp[k]!=){q.push(K);pp[k]=;}

            }

        }

    }

}

int main() {

    memset(w,,sizeof(w));

    cin>>n;

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

    {

        cin>>str[i];

        p[str[i]]=;

    }

    cin>>ch;

    bfs();

    cout<<maxn<<endl;

    return ;

}

下面是我们实验室一个大神写的DFS。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include<functional>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 1000000007

#define inf 0x3f3f3f3f

#define N 1000005

#define maxn 10005

typedef pair<int,int> PII;

typedef long long LL;

int n,m,k,ans,temp;

string str[];

int len[];

int vis[];

int pic[][];

int match(int x,int y){

    int res=;

    int tlen=min(len[x],len[y]);

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

        int j=len[x]-i;k=;

        while(j<len[x]&&k<len[y]&&k<i){

            if(str[x][j]!=str[y][k])break;

            ++j;++k;

        }

        if(k==i){

            res=i;

            break;

        }

    }

    return res==tlen?:res;

}

void init(){

    for(int i=,t;i<=n;++i)

    for(int j=;j<=n;++j){

        if(t=match(i,j)){

            pic[i][j]=t;

        }

    }

}

void dfs(int x){

    if(temp>ans)ans=temp;

    for(int i=;i<=n;++i)if(!vis[i]&&pic[x][i]){

        temp=temp+len[i]-pic[x][i];

        vis[i]=;

        dfs(i);

        vis[i]=;

        temp=temp+pic[x][i]-len[i];

    }

}

int main() {

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

    int i,j,group;

    cin>>n;n<<=;

    for(i=;i<=n;i+=){

        cin>>str[i];

        str[i+]=str[i];

        len[i]=len[i+]=str[i].length();

    }

    char ch;cin>>ch;

    init();

    ans=;

    for(i=;i<=n;++i)if(str[i][]==ch){

        temp=len[i];

        vis[i]=;

        dfs(i);

        vis[i]=;

    }

    cout<<ans<<endl;

    return ;

}

巴特西

单词接龙(dragon)（BFS）