首页 > 代码库 > 单次接龙dfs洛谷

单次接龙dfs洛谷

2024-11-24 10:17:39   202人阅读

题目传送门：https://www.luogu.org/problem/show?pid=1019#sub

典型的爆搜，每次更新最大龙长度即可

搜索每个字符串编号，与已经连接好的字符串进行比较，以此往后找，若全部匹配，则可以接龙

注意：

1.自己也可以与自己相连

2.题目中所说的不能存在包含关系是连接好后的相邻两部分 并不是如果是子串就不能连接 否则第一个单词即起始字母无法连接

//Gang#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cmath>#define FOR(x,y,z) for(int x=y;x<=z;x++)#define ll long longstruct node{    int l,vis;    char s[25];} c[25];int n,maxn=0;using namespace std;void dfs(int x,int l)//x为当前连接好的单词的最后一个单词，l为 目前龙的长度{    FOR(i,1,n)//枚举每个单词的编号    {        if(c[i].vis<2)//一个单词最多被用两次            FOR(j,0,c[x].l)        {            if(c[x].s[j]==c[i].s[0])            {                int k=1;                bool flag=1;                for(int d=j+1; d<c[x].l&&k<c[i].l; k++,d++)                {                    if(c[x].s[d]!=c[i].s[k])                    {                        flag=0;                        break;                    }                }                if(flag)                {                    c[i].vis++;                    dfs(i,l+c[i].l-k);                    c[i].vis--;                }            }        }    }    if(l>maxn)maxn=l;}int main(){    scanf("%d",&n);    FOR(i,1,n)    {        scanf("%s",c[i].s);        c[i].l=strlen(c[i].s);    }    scanf("%s",c[0].s);    c[0].l=strlen(c[0].s);    dfs(0,c[0].l);    printf("%d",maxn);    return 0;}

 

单次接龙dfs洛谷


联系
我们