题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1560
BFS题解：http://www.cnblogs.com/crazyapple/p/3218107.html
构造一个串，使得它包含所有的给定DNA序列，并且要求长度最短。
采用dfs策略，对于每个串定义1个指针，当全部指针为串尾时判断构造的长度，由于状态空间过大，但是又存在冗余搜索，可以用迭代加深将状态减少。最长待构造长度 + 当前长度 < 迭代的最大深度则直接return，大大减少了状态数。
慢慢迭代加深搜索；
代码：
#include<iostream>
#include<stdio.h>
#include<string.h> using namespace std; struct Nod
{
int pos[];
}temp;
int n,len[];
char str[][];
char dna[]="ACGT"; int dfs(Nod tnd,int sum,int depth) //迭代加深搜索
{
int i,j,flag;
Nod nd;
if(sum>depth) return ; //搜索深度超过depth时，表示深度depth太小，还得继续增加
for(i=;i<n;i++) if(len[i]-tnd.pos[i]+sum>depth) return ; //某一个串超过深度depth，len[i]是串本身的长度，tnd.pos[i]为迭代产生的长度，sum为迭代的深度
for(i=;i<n;i++) if(tnd.pos[i]<len[i]) break; //如果某行没有迭代到本身串的长度就break，结合下面if（i==n）判断
if(i==n) return ; //如果i==n，即对i（0，n-1） tnd.pos[i]>=len[i]，全部迭代完成
for(i=;i<;i++)
{
flag = ; //标记是否匹配上
for(j=;j<n;j++)
{
if(str[j][tnd.pos[j]]==dna[i]) //用A C G T去匹配
{
flag = ;
nd.pos[j] = tnd.pos[j] + ; //匹配上了位置向后移动一位
}
else
{
nd.pos[j] = tnd.pos[j];
}
}
if(flag&&dfs(nd,sum+,depth)) return ; //匹配上了，就进行下一层匹配
}
return ;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i;
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%s",str[i]);
len[i] = strlen(str[i]);
}
for(i=;;i++) if(dfs(temp,,i)) break; //i为迭代加深的值，找到则跳出
printf("%d\n",i);
}
return ;
}