台湾菜

HDOJ 2360 Word Ladder

twcai • acm/icpc

BFS+路径保存即可。枚举所有单词作为“第一阶”,找只差一个字母的单词扩展节点,记录该单词前驱,当扩展的单词和第一个单词完全不同时结束BFS。枚举N次,每次碰到比原有情况更短的“阶梯”,就把路径保存下来。题目要求多结果时按字典序输出,只要在读入单词后,对所有单词按字典序排序就可以啦。
有一个比较重要的优化就是对所有单词进行预处理,把只相差一个字母的一对单词和完全不同的一对单词记录下来(我用邻接矩阵保存),然后在进行bfs。在枚举过程中,碰到有阶梯数刚好为l+1的情况,就可以直接结束枚举的过程了(不可能有比l+1更短的情况),由于数据量不大,手打快排和qsort()没太大区别。
#include
#include
#include
using namespace std;
#define OVER 70000
int t,n,l;
char word[101][MAX];
int path[101],root[101];
bool one[110][110],tol[110][110];
bool hash[101],h[27];
struct node{
int num;
int cost;
};
node now,next;
node que[70001];
int ql,qh;

inline void QuickSort(int low, int high)
{
char key[MAX];
int LOW,HIGH;

if(low>high) return ;
strcpy(key,word[low]);
LOW=low;HIGH=high;
while(low {
while(high>low)
{
if(strcmp(key,word[high])>0)
{
strcpy(word[low],word[high]);
low++;break;
}
high--;
}
while(low {
if(strcmp(key,word[low])<0)
{
strcpy(word[high],word[low]);
high--;break;
}
low++;
}
}
strcpy(word[low],key);
QuickSort(LOW,low-1);
QuickSort(low+1,HIGH);
}

//inline int cmp(const void *a,const void *b)
//{
// char* c=(char *)a;
// char* d=(char *)b;
// return strcmp(c,d);
//}

inline int comp(const int &x,const int &y)
{
int c,flag;
memset(h,0,sizeof(h));c=0;
for(int i=0;i {
flag=0;
for(int j=0;j if(!h[j] && word[x][i]==word[y][j])
{c++;h[j]=1;break;}
}
return c;
}

inline int bfs(const int &x)
{
ql=0;qh=0;
now.num=x;now.cost=1;hash[x]=1;
que[qh++]=now;if(qh>OVER) qh%=OVER;
while(ql {
now=que[ql++];if(ql>OVER) ql%=OVER;
if(tol[now.num][x]==1) return now.cost;
for(int i=0;i {
if(hash[i]) continue;
if(one[now.num][i]==1)
{
next.num=i;next.cost=now.cost+1;
que[qh++]=next;if(qh>OVER) qh%=OVER;
hash[i]=1;root[i]=now.num;
}
}
}
return 0;
}

int main()
{
int minpath,tem;

scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&l);
for(int i=0;i scanf("%s",word[i]);
//qsort(word,n,sizeof(word[0]),cmp);
QuickSort(0,n-1);
memset(tol,0,sizeof(tol));
memset(one,0,sizeof(one));
for(int i=0;i for(int j=i+1;j {
tem=comp(i,j);
if(tem==l-1) {one[i][j]=1;one[j][i]=1;}
if(tem==0) {tol[i][j]=1;tol[j][i]=1;}
}
minpath=200;
for(int i=0;i {
memset(hash,0,sizeof(hash));
memset(root,-1,sizeof(root));
path[0]=bfs(i);
if(path[0]>l && path[0] {
minpath=path[0];
for(int j=1;j<=minpath;j++)
{path[j]=now.num;now.num=root[now.num];}
}
}
for(int i=minpath;i>0;i--)
{
if(i==1) printf("%sn",word[path[i]]);
else printf("%s ",word[path[i]]);
}
}
return 0;
}

comments powered by Disqus