首页 > 代码库 > hdu 1560 迭代加深搜索
hdu 1560 迭代加深搜索
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1560
只能说bin神太给力了。。 又学到不少新知识。。
迭代加深搜索,貌似 又叫IDA*, 就是给搜索深度一个限制,搜索到一个满足条件就结束。 注意剪枝~
代码:
#include <iostream>#include <cstdio>#include <cstring>using namespace std;char g[10][10];int size[10];char dna[4] = {‘A‘,‘C‘,‘G‘,‘T‘};int n;int dfs(int now, int l, int p[])//p[i]代表当前第i行字符串匹配了多少个了{ if(now > l) return 0; int maxn = 0; for(int i=0; i<n; i++)//剪枝,查找至少还需要多少深度 { maxn = max(maxn, size[i] -p[i]); } if(maxn == 0) { return now; } if(now + maxn > l) //如果至少需要的深度加上当前的深度比限制深度大,那么就剪掉 return 0; for(int i = 0; i<4; i++) { int flag = 0; int temp[10] = {0}; for(int j = 0; j<n; j++) { if(g[j][p[j]] == dna[i])//满足条件 { flag = 1; temp[j] = p[j] + 1; } else temp[j] = p[j]; } if(flag == 1)//只有满足条件才递归下去 { int t = dfs(now+1, l, temp); if(t != 0) { return t; } } } return 0;}int main(){ int num; cin>>num; int maxn = -1; while(num--) { maxn = -1; memset(size, 0, sizeof(size)); scanf("%d", &n); for(int i=0;i <n; i++) { scanf("%s", g[i]); size[i] = strlen(g[i]); maxn = max(maxn, size[i]); } int ans; int p[10] = {0}; for(int i=maxn; ; i++) { if(dfs(0, i, p)) { ans = i; break; } } cout<<ans<<endl; } return 0;}
hdu 1560 迭代加深搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。