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];
……