本文主要是介绍HDU 1560 IDA*搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用N个串中找到最短的公共串（不要求连续，只要相对位置一样即可）
迭代加深搜索即可
剪枝：当前的深度＋最少还有加深的深度是否大于限制的长度，若是，则退回。
#include "stdio.h"
#include "string.h"const char ch[10]="ATCG";
int deep,n;
char s[10][10];
int pos[10];//记录第i个序列正在使用第几个位置int Max(int a,int b)
{if (a<b) return b;else return a;
}int get_h()
{int ans,i;ans=0;for (i=0;i<n;i++)ans=Max(ans,strlen(s[i])-pos[i]);//找出在当前情况下最长的未被匹配的长度估测长度return ans;
}
int dfs(int w)
{int h,i,j,flag;int temp[10];h=get_h();if(w+h>deep) return 0;//当前长度+估测的长度比deep还大的话，也就没有继续往下搜索的必要了if(h==0) return 1;for (i=0;i<4;i++) //枚举当前位置的4个字母{flag=0;for (j=0;j<n;j++)temp[j]=pos[j];//先将pos保存起来for (j=0;j<n;j++)if (s[j][pos[j]]==ch[i])//当前这位符合，则该串的位置往后移一位{flag=1;pos[j]++;}if (flag==1)//有符合的，则往下搜索{if (dfs(w+1)==1) return 1;for (j=0;j<n;j++)//还原pos[j]=temp[j];}}return 0;
}
int main()
{int Case,i;scanf("%d",&Case);while (Case--){scanf("%d",&n);deep=0;for (i=0;i<n;i++){scanf("%s",s[i]);deep=Max(deep,strlen(s[i]));pos[i]=0;}while (1){if (dfs(0)==1) break;deep++;}printf("%d\n",deep);}return 0;
}
这篇关于HDU 1560 IDA*搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
