题目意思 是任何只有一个字母不同的单词可以进行改变 最后要转换成全部不同的单词 根据理论每次转换的最小步长应该为单词长度
题目要求输出最小字典序的序列~~~
只要对输入的单词进行排序就能保证 然后首先建2张图 一张是只改变一个字母能变换的路径图 一个是都不相同单词之间的图
很好 下面就是BFS 使用一个数组保存父亲节点 找到后输出就可以了~~~
注意下BFS如果采用逐层遍历的话 使用阀值降低规模
以下是代码:
#include <iostream>
#include <queue>
#include <string>
using namespace std;
{
char key[30];
}Info;
{
Info *a = (Info *)p1;
Info *b = (Info *)p2;
return strcmp(a->key,b->key);
} long n,l;
long now[110];
long path[110];
bool One[110][110];
bool Map[110][110];
Info Data[110];
long tp[110];
{
long i,j,res;
memset(tp,0,sizeof(tp));
res=0;
for(i=0;i<l;++i)
{
for(j=0;j<l;++j)
{
if(!tp[j]&&a.key[i]==b.key[j])
{
++res;
tp[j]=1;
break;
}
}
}
return l-res;
}
{
long now;
long pre;
long step;
}Node;
long hash[110];
{
long i,j,len;
long cost=INT_MAX;
long pos=-1;
{
while (!q.empty())
{
q.pop();
}
{
now[j]=j;
hash[j]=INT_MAX;
}
Start.step=0;
Start.pre=i;
q.push(Start);
{
while (!save.empty())
{
save.pop();
}
{
Node t=q.front();
q.pop();
{
continue;
}
now[t.now]=t.pre;
if (Map[i][t.now])
{
if (t.step<cost)
{
cost=t.step;
memcpy(path,now,sizeof(path));
pos=t.now;
if (cost==l)
{
goto l1;
}
}
break;
}
{
if (One[t.now][j]&&t.step+1<hash[j])
{
Node n;
n.pre=t.now;
n.now=j;
n.step=t.step+1;
save.push(n);
}
}
{
q.push(save.front());
save.pop();
}
}
string res;
bool begin=true;
{
if (begin)
{
res=string(Data[pos].key);
begin=false;
}
else
{
res=string(Data[pos].key)+string(" ")+res;
}
pos=path[pos];
}
{
res=string(Data[pos].key);
}
else
{
res=string(Data[pos].key)+string(" ")+res;
}
puts(res.data());
res.erase();
} int main()
{
long T;
scanf("%ld",&T);
{
long i,j;
scanf("%ld %ld",&n,&l);
getchar();
{
gets(Data[i].key);
}
memset(One,0,sizeof(One));
memset(Map,0,sizeof(Map));
{
for (j=i+1;j<n;++j)
{
long num=check(Data[i],Data[j]);
if(num==1)
{
One[i][j]=One[j][i]=true;
}
if (num==l)
{
Map[i][j]=Map[j][i]=true;
}
}
}
}
#include <queue>
#include <string>
using namespace std;
typedef
struct{
char key[30];
}Info;
inline
int cmp(const void *p1, const void *p2){
Info *a = (Info *)p1;
Info *b = (Info *)p2;
return strcmp(a->key,b->key);
} long n,l;
long now[110];
long path[110];
bool One[110][110];
bool Map[110][110];
Info Data[110];
long tp[110];
inline
long check (Info a,Info b){
long i,j,res;
memset(tp,0,sizeof(tp));
res=0;
for(i=0;i<l;++i)
{
for(j=0;j<l;++j)
{
if(!tp[j]&&a.key[i]==b.key[j])
{
++res;
tp[j]=1;
break;
}
}
}
return l-res;
}
typedef
struct{
long now;
long pre;
long step;
}Node;
queue
<Node> q,save;long hash[110];
inline
void BFS(){
long i,j,len;
long cost=INT_MAX;
long pos=-1;
for (i=0;i<n;++i)
{
while (!q.empty())
{
q.pop();
}
for (j=0;j<n;++j)
{
now[j]=j;
hash[j]=INT_MAX;
}
Node Start;
Start.now
Start.step=0;
Start.pre=i;
q.push(Start);
len
=0;while (!q.empty()&&++len<=cost)
{
while (!save.empty())
{
save.pop();
}
while (!q.empty())
{
Node t=q.front();
q.pop();
if (t.step>=hash[t.now])
{
continue;
}
hash[t.now]
=t.step;now[t.now]=t.pre;
if (Map[i][t.now])
{
if (t.step<cost)
{
cost=t.step;
memcpy(path,now,sizeof(path));
pos=t.now;
if (cost==l)
{
goto l1;
}
}
break;
}
for (j=0;j<n;++j)
{
if (One[t.now][j]&&t.step+1<hash[j])
{
Node n;
n.pre=t.now;
n.now=j;
n.step=t.step+1;
save.push(n);
}
}
}
while (!save.empty())
{
q.push(save.front());
save.pop();
}
}
}
l1:
string res;
bool begin=true;
while (pos!=path[pos])
{
if (begin)
{
res=string(Data[pos].key);
begin=false;
}
else
{
res=string(Data[pos].key)+string(" ")+res;
}
pos=path[pos];
}
if (begin)
{
res=string(Data[pos].key);
}
else
{
res=string(Data[pos].key)+string(" ")+res;
}
puts(res.data());
res.erase();
} int main()
{
long T;
scanf("%ld",&T);
while (T--)
{
long i,j;
scanf("%ld %ld",&n,&l);
getchar();
for (i=0;i<n;++i)
{
gets(Data[i].key);
}
qsort(Data,n,
sizeof(Info),cmp);memset(One,0,sizeof(One));
memset(Map,0,sizeof(Map));
for (i=0;i<n;++i)
{
for (j=i+1;j<n;++j)
{
long num=check(Data[i],Data[j]);
if(num==1)
{
One[i][j]=One[j][i]=true;
}
if (num==l)
{
Map[i][j]=Map[j][i]=true;
}
}
}
BFS();
}
return 0;
}