//IDA*,启发函数为当前最多的距离结尾的差距
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int pos[N];//每一个posi都指向第i个字符串
int len[N];//用来存每个串的长度
char g[N][N];
string s = "ACGT";//我们构造的一个母串
bool dfs(int depth,int max_depth,int pos[])
{
int maxx = 0;
//找到最靠前的指针,即为最不符合条件的串的pos到末尾的距离,启发函数
for(int i = 0; i < n; i++)maxx = max(maxx,len[i] - pos[i]);
if(maxx + depth > max_depth)return false;//IDA*
if(maxx == 0 && depth <= max_depth)return true;
int temp[N];//记录每一层的指针情况(注意不能直接改pos,因为我们会回溯,要恢复现场)
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < n; j ++)
{
//首先要明白,选一个字母可能会使序列中的某个字母的指针后移
//选这个字母对于这个字符串"成功"
if(g[j][pos[j]] == s[i])
{
temp[j] = pos[j] + 1;
}
else temp[j] = pos[j];
}
if(dfs(depth + 1,max_depth,temp))return true;
}
return false;
}
int main()
{
int t;cin >> t;
while(t --)
{
cin >> n;
for(int i = 0; i < n; i ++)
{
scanf("%s",g[i]);
len[i] = strlen(g[i]);//存一下每个字符串的长度
}
//迭代加深
int depth = 0;
memset(pos,0,sizeof pos);//将指针全部指向开头
while(!dfs(0,depth,pos))depth ++;//当前搜索的深度,最大限度,每一层的指针
cout << depth << endl;
}
return 0;
}
下面是对pos的解释
所以当每一层的pos都指向末尾时即为答案
思考:我们用一个数组来模拟对每一个字符串的指针,也减少了回溯的麻烦,巧妙!