题解 P1019 【单词接龙】

_KaQqi · 2019-05-04 16:11:32 · 题解

这道题n很小，用深度优先搜索不会超时。 基本思路就是深度优先搜索，也就是暴力枚举。。 感觉这道题的难点其实不在dfs，而在字符串... 直接上代码。

#include <stdio.h>
#include <string.h>

int n;
char began[20];
char data[21][21];
char used_time[21];
int result = 0;

int CheckSame(char* a,char*b)//检查的相同字符，返回相同个数。如果无法接上，return 0，反之return相同个数
{
    int count = 0;
    int long_a = strlen(a);
    int long_b = strlen(b);
    for(unsigned int i = 0;i<long_a&&i<long_b;i++)//相同字符再长也长不过两个词，这层循环是定位相同地址的
    {
        int is_same = 1;
        for(unsigned int j = 0;j<=i;j++)//这层循环是判断是否相同的
        {
            if (a[long_a - i + j-1] != b[j])
            {
                is_same = 0;
                break;
            }
        }
        if(is_same == 0) continue;
        else//这个函数要取的是最小的相同个数，而不是最大，因为取的越小，接的越长
        {
            count = i +1;
            return count;
        }
    }
    return count;
}

int dfs(char* start_letter,int count)//长度计算式为：加上未出现的单词长度减去重复长度
{
    if(count > result) result = count;//时刻准备更新result
    for (int i = 1;i<=n;i++)
    {
        if (used_time[i] < 2 && CheckSame(start_letter,data[i]))//满足使用小于2次并且可以接上就可以用。
        {
            used_time[i] ++;
            dfs(data[i],count + strlen(data[i])-CheckSame(start_letter,data[i]));//根据长度计算式，可以知道要传的长度是count + strlen(data[i])-CheckSame(start_letter,data[i]）
            used_time[i] --;
        }
    }
    return 0;
}

int main()
{
    scanf("%d",&n);
    for (int i = 1;i<=n;i++)
    {
        scanf("%s",&data[i]);
    }
    scanf("%s",&began);
    dfs(began,strlen(began));
    printf("%d",result);
    return 0;
}

我的代码其实也有很多不足之处，比如那个CheckSame函数是O(n^2)的，算一次消耗很大，如果能记到数组里就能提高很大的效率。。反正不提高也没事，n撑死了就20嘛