word ladder

#include <iostream>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <vector>
#include <deque>
#include <functional>
#include <stdint.h>

using namespace std;

typedef unordered_set<string> dict_t;
typedef unordered_map<int, vector<int> > graph_t;

typedef uint16_t vertex_t;
typedef uint32_t edge_t;
typedef std::unordered_set<edge_t> edge_set_t;


edge_t make_edge(vertex_t i, vertex_t j)
{
    if(i > j) { swap(i,j); }
    return ((0xFFFF&i)<<16) + (0xFFFF&j);
}

void connect(graph_t & G, edge_set_t & edges, vertex_t i, vertex_t j)
{
    G[i].push_back(j);
    G[j].push_back(i);
    edges.insert(make_edge(i,j));
}

class Solution {
public:

    int distance(const vector<string> & svec, int a, int b,
        size_t word_len)
    {
        const string & sa = svec[a];
        const string & sb = svec[b];

        const size_t & N = word_len;

        if(a > b) { std::swap(a,b); }

        int num_diff = 0;
        size_t i;

        for(i=0; i < N/2; ++i)
        {
            if(sa[i] != sb[i] && ++num_diff > 1)
            {
                return num_diff;
            }
            if(sa[N-1-i] != sb[N-1-i] && ++num_diff > 1)
            {
                return num_diff;
            }
        }
        if(N%2 != 0 && sa[N/2] != sb[N/2] && ++num_diff > 1)
        {
            return num_diff;
        }
        return num_diff;
    }

    typedef dict_t::iterator dict_pos_t;

    int ladderLength(string start, string end, dict_t &dict)
    {
        const size_t word_len = start.size();

        start += 's';
        end += 'e';

        dict.insert(start);
        dict.insert(end);

        const size_t NUM_WORDS = dict.size();
        vector<string> svec(NUM_WORDS);

        dict_t::iterator it = dict.begin();

        size_t start_pos, end_pos;

        std::hash<std::string> hash_fn;

        const size_t start_hash = hash_fn(start);
        const size_t end_hash = hash_fn(end);

        for(size_t i = 0; it != dict.end(); ++it, ++i)
        {
            const string & S = *it;
            const size_t h = hash_fn(S);
            if(h == start_hash) { start_pos = i; }
            if(h == end_hash) { end_pos = i; }
            svec[i] = S;
        }

        bool entrance_found = false, exit_found = false;
        graph_t G;

        edge_set_t edges;

        for(size_t i = 0; i < NUM_WORDS; ++i)
        {
            if(i == start_pos || i == end_pos) { continue; }

            int d;

            d = distance(svec, start_pos, i, word_len);
            if(d == 1)
            {
                //connect(G, edges, start_pos, i);
                entrance_found = true;
            }

            d = distance(svec, end_pos, i, word_len);
            if(d == 1)
            {
                //connect(G, edges, end_pos, i);
                exit_found = true;
            }

        }

        if(!entrance_found || !exit_found) { return 0; }

        for(size_t i = 0; i < NUM_WORDS-1; ++i)
        {
            for(size_t j = i+1; j < NUM_WORDS; ++j)
            {
                if(edges.find(make_edge(i,j)) != edges.end()) { continue; }

                const string & si = svec[i];
                const string & sj = svec[j];
                int d = distance(svec, i, j, word_len);
                if(d == 1)
                {
                    connect(G, edges, i, j);
                }
            }
        }


        return bfs(G, start_pos, end_pos);
    }

    int bfs(graph_t & G, int start, int end)
    {
        std::deque<int> Q;
        std::deque<int> Depth;

        std::unordered_set<int> visited;

        Q.push_back(start);
        Depth.push_back(1);

        while(!Q.empty())
        {
            int vertex = Q.front();
            int depth = Depth.front();

            Q.pop_front();
            Depth.pop_front();

            if(vertex == end) { return depth; }

            if(visited.find(vertex) != visited.end()) { continue; }

            visited.insert(vertex);

            graph_t::iterator it = G.find(vertex);
            if(it == G.end()) { continue; }
            const std::vector<int> & siblings = it->second;
            for(size_t i = 0; i < siblings.size(); ++i)
            {
                Q.push_back(siblings[i]);
                Depth.push_back(depth+1);
            }
        }
        return 0;
    }
};