Word Ladder是这样一个游戏，给定一个字典，从中任意取出两个单词（这两个单词没有任何字母相等），操作者只允许每次变换一个字母，而且变换后的单词应该在字典里，经过若干步变换出目的单词。求一种最少的变换方案，这个游戏在西方还是比较流行的。

今天在HOJ的练习赛上又看到了这样的题目，不过题目有点区别，要求输出变换次数最少而且字典序最小的变换方案。如果是纯粹做比赛，应该是用广度优先的搜索方法搜索结果。

采用最短路的Dijkstra算法也能求解Word Ladder的游戏，可惜不能保证一定是安最小的字典序输出的。

＃i nclude <stdio.h>
＃i nclude <string.h>
＃i nclude <ctype.h>
＃i nclude <stdlib.h>

#define maxn 101
#define maxr 300000

int map[maxn][maxn];
char dic[maxn][30];
int n,l,res_count,first;

int father[maxn];
char buf[maxn*30],res_buf[maxn*30];

//判断两个字符串是不是只有1个字符不同
int one_diff(char *s1,char *s2){
    int flag,i,j,count;
    int tmp[26];
 memset(tmp,0,sizeof(tmp));
 count=0;
 for (i=0; s1[i]!='\0'; ++i){
  for (j=0; s2[j]!='\0'; ++j){
   if (s1[i]==s2[j] && !tmp[j]){
    tmp[j]=1;
    ++count;
    break;
   }
  }
 }
 if (count==strlen(s1)-1)
  return 1;
 return 0;
}
//判断两个字符串是不是全部字符都不相同
int diff(char *s1,char *s2){
    int i,j,k,flag;
    int tmp1[26],tmp2[26];
    memset(tmp1,0,sizeof(tmp1));
    memset(tmp2,0,sizeof(tmp2));
    for (i=0; s1[i]!='\0'; ++i){
        tmp1[s1[i]-'a']++;
    }
    for (i=0; s2[i]!='\0'; ++i){
        tmp2[s2[i]-'a']++;
    }
    flag=1;
    for (i=0; i<26; ++i){
        if (tmp1[i] && tmp2[i]){
            return 0;
        }
    }
    return 1;
}

//最短路算法求其中的一条路径
int dijkstra(int n, int st, int ed){
    int minver, rec[maxn];
    int i, v[maxn],cur = st;
    memset(v, 0, sizeof(v));
    for (i = 0; i < maxn; ++i) rec[i] = 0x7ffffff;
         rec[st] = 0;
    father[cur]=st;
    while (cur != ed) {
        v[cur] = 1;
        for (i = 0; i < n; ++i) {
            if (!v[i] && map[cur][i] && rec[i]>rec[cur]+map[cur][i]){
                rec[i] = rec[cur] + map[cur][i];
                father[i]=cur;
            }
        }
        for (i = 0, minver = 0x7ffffff; i < n; ++i)
            if (minver > rec[i] && !v[i]) {
                minver = rec[i];
                cur = i;
        }
        if (minver == 0x7ffffff) break;
    }
    return rec[ed];
}
//计算最短路径上的结点
int queue[maxn];
void path(int st,int ed){
    int i,j,pos,count;
    buf[0]='\0';
    queue[0]=ed;
    pos=father[ed];
    count=1;
    while (pos!=st){
        queue[count++]=pos;
        pos=father[pos];
    }
    queue[count++]=st;
    /*for (i=count-1; i>=0; --i){
        strcat(buf,dic[queue[i]]);
        printf("%d",queue[i]);
        if (i)
            printf("->");
    }
    printf("\n");*/
 for (i=count-1; i>=0; --i){
        strcat(buf,dic[queue[i]]);
       // printf("%s",dic[queue[i]]);
       // if (i)
        //    printf("->");
    }
    //printf("\n");
    if (first==0){
        strcpy(res_buf,buf);
        first=1;
        return ;
    }
    if (strlen(res_buf)>strlen(buf)){
        strcpy(res_buf,buf);
    }
    else if (strlen(res_buf)==strlen(buf)){
        if (strcmp(res_buf,buf)>0){
            strcpy(res_buf,buf);
        }
    }
    //printf("%s\n",buf);
}

int main(){
    int kase,i,j,min,cur;
 char buf1[]="agbhda";
 char buf2[]="bheaag";
 printf("comp=%d\n",one_diff(buf1,buf2));
    scanf("%d",&kase);
    while (kase--){
        scanf("%d%d",&n,&l);
        for (i=0; i<n; ++i){
            scanf("%s",dic[i]);
        }
        for (i=0; i<n; ++i){
            for (j=0; j<n; ++j){
                map[i][j]=0x7ffffff;
            }
        }
        //构建图形
  for (i=0; i<n-1; ++i){
            for (j=i+1; j<n; ++j){
                if (one_diff(dic[i],dic[j])){
                    map[i][j]=map[j][i]=1;
                }
            }
        }
        min=0x7ffffff;
        first=0;
       
        buf[0]='\0';
        res_buf[0]='\0';
       
        for (i=0; i<n; ++i){
            for (j=0; j<n; ++j){
                if (i==j){
                    continue;
                }
                if (diff(dic[i],dic[j])){
                    cur=dijkstra(n,i,j);
                    if (cur==0x7ffffff){
                        continue;
                    }
     //printf("from %d to %d is %d\n",i,j,cur);
                    path(i,j);   
           
                }
            }       
        }
        first=0;
        for (i=0; i<l; ++i)
            printf("%c",res_buf[i]);
        for (; res_buf[i]!='\0'; i+=l){
            printf(" ");
            for (j=0; j<l; ++j)
                printf("%c",res_buf[i+j]);
        }
        printf("\n");
        //printf("%s\n\n",res_buf);
    }
    return 0;
}