http://proggitquiz.com/challenge/5/

words.cpp

#include <iostream>
#include <vector>
#include <map>
#include <queue>

#define foreach(x, it) for (typeof(x.begin()) it = x.begin(); it != x.end(); ++it)

#define WORD_SIZE 5

using namespace std;

map<string, int> lookup;
vector<string> words;
vector< vector<int> > graph;
vector<int> parent;
vector<bool> visited;

bool bfs(int src, int dst)
{
	visited.clear();
	visited.resize(words.size());
	parent.resize(words.size());

	queue<int> q;
	q.push(src);

	while (!q.empty()) {
		int node = q.front();
		q.pop();

		if (node == dst)
			return true;

		foreach (graph[node], it) {
			if (!visited[*it]) {
				q.push(*it);
				parent[*it] = node;
				visited[*it] = true;
			}
		}
	}

	return false;
}

void find_ladder(string word1, string word2)
{
	int dst = lookup[word1];
	int src = lookup[word2];

	if (!bfs(src, dst)) {
		cout << "not found!" << endl;
		return;
	}

	int len = 0;
	for (;;) {
		cout << words[dst] << endl;
		if (dst == src)
			break;
		dst = parent[dst];
		len++;
	}
	cout << len << endl;
}

void build_graph()
{
	graph.resize(words.size());

	foreach (words, w) {
		int index = lookup[*w];

		for (int i=0; i<WORD_SIZE; i++) {
			for (int c = 'a'; c <= 'z'; c++) {
				string word = *w;
				word[i] = c;

				if (word == *w)
					continue;

				map<string, int>::iterator it = lookup.find(word);
				if (it != lookup.end())
					graph[index].push_back(it->second);
			}
		}
	}
}

void read_words()
{
	string word;
	int i = 0;

	while ((cin >> word)) {
		words.push_back(word);
		lookup[word] = i++;
	}
}

int main()
{
	read_words();
	build_graph();

	find_ladder("scale", "cloud");

	return 0;
}

ainda se divertindo com competições?