首页 > 代码库 > 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 迭代加深搜索