首页 > 代码库 > HRBUST2030(dfs)
HRBUST2030(dfs)
成语接龙
Time Limit: 1000 MS Memory Limit: 32768 KB
64-bit integer IO format: %lld , %llu Java class name: Main
[Submit] [
c=problem-status&problem_id=131971" style="background-color:transparent; color:rgb(66,139,202); text-decoration:none">Status] [Discuss]
题目链接:http://acm.hrbust.edu.cn/vj/index.php?c=problem-problem&id=131971
Description
给出N个成语,通过成语接龙,求接出最长龙的成语个数。
每一个成语由至少三个至多8个汉字组成,假设前一个成语的最后一个字和后一个成语的第一个字同样,那么就能够接到一起。
为了将问题简化,每一个汉字用4个字母编码取代。保证每一个汉字的都有唯一的编码。全部字母均为小写字母,且以第一个成语为開始成语, 每一个成语仅仅能够使用一次。
每一个成语由至少三个至多8个汉字组成,假设前一个成语的最后一个字和后一个成语的第一个字同样,那么就能够接到一起。
为了将问题简化,每一个汉字用4个字母编码取代。保证每一个汉字的都有唯一的编码。全部字母均为小写字母,且以第一个成语为開始成语, 每一个成语仅仅能够使用一次。
Input
多组測试数据,对每组数据
第一行是一个整数N。代表有N个成语。
接下来N行,每行一个成语。
(N <= 20)
第一行是一个整数N。代表有N个成语。
接下来N行,每行一个成语。
(N <= 20)
Output
输出最长长度
Sample Input
5
adfkejimejlsgkeh
emiemkwlcuhelmge
gkeheohowehiemie
lmgejoewijfeabcd
emiekejlwejdadfk
Sample Output
4
解题思路:
这道题读题是个坎·····首先注意要存的是每一个字符串的前4个字母和后四个字母,然后要注意每次接龙都是以第一个成语为開始。
读题过后。就能够開始考虑求解了。题目要求输出最长长度,非常明显会出现第一个单词取完取第三个单词。然后发现此时我能够连第二个单词这样的情况,这就是一种回溯。所以以第一个单词为起点,用dfs把n-1个串搜一遍。
这里又从LSJ那里学到一个好思想,把它想象成一棵树。最后求最深的高度。每次搜索时用vis做个标记,两个原则:(1)标记过的我不走(2)和当前key值同样的点我不走。
每次更新max_cnt。注意递归时++step和1+step的差别。假设写成++step,那么会改变step的值,同层的节点高度会改变;反之,假设是1+step。那么step值不会变,当扫完一个节点后。能够按原来的step值訪问同层的其它节点。
完整代码:
#include <functional> #include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cstring> #include <climits> #include <cassert> #include <complex> #include <cstdio> #include <string> #include <vector> #include <bitset> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <list> #include <set> #include <map> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") typedef long long LL; typedef double DB; typedef unsigned uint; typedef unsigned long long uLL; /** Constant List .. **/ //{ const int MOD = int(1e9)+7; const int INF = 0x3f3f3f3f; const LL INFF = 0x3f3f3f3f3f3f3f3fLL; const DB EPS = 1e-9; const DB OO = 1e20; const DB PI = acos(-1.0); //M_PI; string str; int n; int vis[100001]; struct node { string start; string ends; }q[100001]; int max_cnt; int dfs(int key , int step , int &max_cnt) { for(int i = 0 ; i < n ; i ++) { if(vis[i] == 0 && i != key) { if(q[key].ends == q[i].start) { vis[i] = 1; int t = dfs(i , 1+step , max_cnt); vis[i] = 0; max_cnt = max(max_cnt , t); } } } return step; } int main() { #ifdef DoubleQ freopen("in.txt","r",stdin); #endif while(~scanf("%d",&n)) { for(int i = 0 ; i < n ; i ++) { cin >> str ; int len = str.length(); q[i].start = ""; q[i].start += str[0]; q[i].start += str[1]; q[i].start += str[2]; q[i].start += str[3]; q[i].ends = ""; q[i].ends += str[len-4]; q[i].ends += str[len-3]; q[i].ends += str[len-2]; q[i].ends += str[len-1]; } memset(vis , 0 , sizeof(vis)); max_cnt = 0; vis[0] = 1; int step = 0; dfs(max_cnt , step , max_cnt); printf("%d\n",max_cnt+1); } }
HRBUST2030(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。