蓝桥杯算法训练VIP-单词接龙 （C语言代码）

解题思路:dfs

注意事项:我开始提交的时候本以为会错的，结果对了。有一个情况没考虑到位举个例子比如abcdd，ddfgh，将它们单词接龙应该是abcddfgh吧，代码跑出来是abcdddfgh，多了一位。不知道怎么回事还是是对的。迷

参考代码:

#include<stdio.h>

#include<string.h>

#define MAX 10010

int n;

int max=0;

char blong[MAX+1];

char word[21][MAX+1];

int vis[21]={0};

int check(int x,char a[MAX+1])

{

int i,j,k;

int len=0;

int len2=0;

len=strlen(a)-1; 

len2=strlen(word[x])-1;

for(i=len;i>=0&&len2;i--,len2--)

{

if(a[i]==word[x][0])

{

// while(a[len]==a[i-1])

// i--;

k=1;

for(j=i+1;j<=len;j++)

{

if(a[j]!=word[x][k])

break;

k++;

}

if(j>len)

return i;//返回龙的部位 

}

}

return 0;

}

void dfs(char a[MAX+1])

{

int i,j,sum=0;

int len=0,llong,flag=0;

char add[MAX+1];

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

{

if(vis[i]<2)

{

len=check(i,a);

if(len)

{

//把龙接上去

for(j=0;j<len;j++)

{

add[j]=a[j];

  } 

    strcat(add,word[i]);

    vis[i]++;

    dfs(add);

  vis[i]--;

  memset(add,0,sizeof(add));

}

}

len=strlen(a);

if(len>max)

{ 

max=len;

// printf("%s\n",a);

}

}

return;

} 

int main()

{

int i;

scanf("%d",&n);

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

scanf("%s",&word[i]);

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

    {

    if(word[i][0]==word[n][0])

    {

    vis[i]++;

    dfs(word[i]);

    vis[i]--;

}

}

printf("%d\n",max);

return 0;

}