【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（10）

目录

写在前面：

题目：P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

---

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1019 [NOIP2000 提高组] 单词接龙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输入的第一行为一个单独的整数 n 表示单词数，

以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出格式：

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

输入样例：

5
at
touch
cheat
choose
tact
a

输出样例：

23

解题思路：

我们使用深度优先搜索的时候，

第一个要注意的点是搜索的顺序，

因为我们要保证，

我们写出的递归结构能够遍历所有情况。

（以上递归搜索的基本思路，多熟悉总是好的）

 接下来是具体思路：

根据题意，我们需要解决一些问题：

1. 怎样记录每个单词的使用个数

可以开一个数组来记录，小问题，

2. 怎样判断一个单词能接到另一个单词上？

到时候我们具体情况具体分析，

3. 如何遍历所有情况？

以题目的例子为例：

这个是根据这样的规律往下搜索的：

 单词两两拼接，

 下面是代码实现：

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
const int N = 30;
 
int n;
 
//接收字母
string arr[N];
 
//计算字母用了几次
int used[N];
 
//龙
char head;
 
//第i个单词是否能接到第j个单词后面，g[i][j]的值存的是他们重合的长度
int g[N][N];
 
//计算最长的字符串
int res;
 
void dfs(string dragon, int x)
{
    res = max(res, (int)dragon.size());
    
    used[x]++;//计算单词使用次数
    for(int i = 0; i < n; i++)
    {
        //如果能拼接，且该单词使用次数<2
        if(g[x][i] && used[i] < 2)
        {
            //减去重复部分并拼接
            dfs(dragon + arr[i].substr(g[x][i]), i);
        }
    }
    used[x]--;//恢复现场
}
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    cin >> head;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            //第i个单词        第j个单词
            string a = arr[i], b = arr[j];
            for(int k = 1; k < min(a.size(), b.size()); k++)
            {
                //如果能接到后面，就记录下来
                if(a.substr(a.size() - k, k) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
            }
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        //从第一个字母是龙的单词开始
        if(arr[i][0] == head)
        {
            dfs(arr[i], i);
        }
    }
    
    printf("%d", res);
    return 0;
}

AC ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。