DFS -- 1

P1019 [NOIP 2000 提高组] 单词接龙

https://www.luogu.com.cn/problem/P1019

来发题解的

首先看题目会觉得很简单，但是要怎么用代码实现呢。

字符串这个东西本质其实和数组差不多，只要我们掌握一些语法和函数

substr(x,y)

这是一个可以取出字符串任意一个部分的函数

第一个参数 x -- 代表要截字符串的起始位置

第二个参数 y -- 代表要截字符串的长度

比如 t = 'string' , t.substr(0,2) 就是 st

还有一个用法，比如 substr(4) 就是 ng //从位置4开始到结尾的子字符串

//字符串默认是从0开始索引的

有了这个函数，这个题目就会简单很多，接下来我们继续思考

1.怎么找到对应相等的部分，并接起来

2.怎么递归，要传递什么参数下去，即怎么去dfs。

----首先我们要先找到龙头，即第一个字母的对应，这样才会进行dfs

这很简单，我们只需一个for循环的判断即可。

然后进行匹配，当找到两个字符串相对应的两个部分，就把加起来，再进行dfs

#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int N = 39; int n,ans = 0; char c; string ss[N]; int v[N] = {0}; void dfs(string s){ int ank = s.size(); ans = max(ans,ank); for(int i = 1 ; i <= n ; i++){ if(v[i] == 2) continue; //每个字符串最多只能被用一次 for(int j = 1 ; j <= min(s.size(),ss[i].size()) ; j++){ if(s.substr(s.size() - j) == ss[i].substr(0,j)){ v[i] ++; dfs(s + ss[i].substr(j));//把后面不相等的部分给接上 v[i] --; } } } } void solve(){ cin>>n; for(int i = 1 ; i <= n ; i++) cin>>ss[i]; cin>>c; for(int i = 1 ; i<= n ; i++){ if(ss[i][0] == c){ v[i] ++; dfs(ss[i]); v[i]--; // 回溯 } } cout<<ans; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } return 0; }