using System;

using System.Collections.Generic;

public class Program

{

    // http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/

    public static void Main()

    {

        var dict = new HashSet<string> { "hot","dot","dog","lot","log" };

        var start = "hit";

        var end = "cog";

        var ladders = findLadders(start, end, dict);

        foreach (var ladder in ladders) {

            var l = "|";

            foreach (var w in ladder)

                l += w + "|";

            Console.WriteLine(l);

        }

    }

    private static List<LinkedList<string>> findLadders(string start, string end, HashSet<string> dict) {

        var visited = new HashSet<string>();

        var unvisited = new HashSet<string>();

        var minSteps = 0; // min steps to do to reach the end word in this ladder?

        var preSteps = 0; // SAY WHAT

        var q = new Queue<WordNode>();

        var result = new List<LinkedList<string>>();

        dict.Add(end);

        foreach (var d in dict) unvisited.Add(d);

        q.Enqueue(new WordNode(start, 0, null));

        while (q.Count > 0) {

            var top = q.Dequeue();

                                                                                                Console.WriteLine(top.Word);

            var curSteps = top.Steps; // # steps in the current ladder

            // check if we found the end word

            if (top.Word == end) {

                // check WAT?

                if (minSteps == 0) minSteps = top.Steps;

                if (minSteps == top.Steps && minSteps != 0) { // HOW IS THIS POSSIBLE

                    // reconstruct the ladder and store it into result

                    // unwind from last to first, placing previous one at the front of the linked list

                    var l = new LinkedList<string>();

                    l.AddFirst(top.Word);

                    while(top.Pre != null) {

                        l.AddFirst(top.Pre.Word);

                        top = top.Pre;

                    }

                    result.Add(l);

                    continue;

                }

            }

            // I DONT GET IT

            if (preSteps < curSteps) {

                unvisited.ExceptWith(visited);

            }

            preSteps = curSteps;

            // while not found, find the next step

            var w = top.Word.ToCharArray();

            for (var i = 0; i < w.Length; i++) {

                var tempC = w[i];

                for (var c = 'a'; c <= 'z'; c++) {

                    w[i] = c;

                                                                                            Console.WriteLine(w.);

                    if (dict.Contains(w.ToString())) {

                        q.Enqueue(new WordNode(w.ToString(), top.Steps + 1, top));

                        visited.Add(w.ToString());

                    }

                }

                w[i] = tempC;

            }

        }

        return result;

    }

    class WordNode {

        public string Word {get; private set;}

        public int Steps {get; private set; }

        public WordNode Pre {get; private set; }

        public WordNode(string word, int steps, WordNode pre) {

            Word = word;

            Steps = steps;

            Pre = pre;

        }

    }

}