public class Solution {
    int min=Int32.MaxValue;
    public int OpenLock(string[] deadends, string target) {
        HashSet<string> dead=new HashSet<string>();
        foreach (string i in deadends)
            dead.Add(i);

        bfs("0000",target,dead);
        return min==Int32.MaxValue?-1:min;
    }

    void bfs(string source,string destination,HashSet<string> deadends)
    {

        if (deadends.Contains(source))
            return;
        Queue<string> q=new Queue<string>();
        q.Enqueue(source);
        Dictionary<string, int> visited = new Dictionary<string, int>();
        visited.Add("0000", 0);

        while (q.Count>0)
        {
            source=q.Dequeue();
            int depth = visited[source];
            if (source==destination)
            {
                min=depth;
                return;
            }



            List<string> neighbours=GetNeighbours(source);
            for (int i=0;i<neighbours.Count;i++)
            {
                if (visited.ContainsKey(neighbours[i]))
                    continue;

                if (deadends.Contains(neighbours[i]))
                    continue;

                if (!visited.ContainsKey(neighbours[i]))
                    visited.Add(neighbours[i],depth+1);

                q.Enqueue(neighbours[i]);

            }

        }

    }

    List<string> GetNeighbours(string s)
    {
        List<string> neighbours=new List<string>();
        for (int i=0;i<s.Length;i++)
        {
            StringBuilder sb=new StringBuilder(s);
            if (s[i]=='0')
            {
                sb[i]='1';
                neighbours.Add(sb.ToString());

                sb[i]='9';
                neighbours.Add(sb.ToString());
            }
            else if (s[i]=='9')
            {
                sb[i]='8';
                neighbours.Add(sb.ToString());

                sb[i]='0';
                neighbours.Add(sb.ToString())  ;
            }else
            {

                sb[i]=(char)(((int)s[i]) + 1);
                neighbours.Add(sb.ToString());

                sb[i]=(char)(((int)s[i]) - 1);
                neighbours.Add(sb.ToString());
            }

        }

        /*foreach(string i in neighbours)
        {
            Console.Write(i+" ");
        }
        Console.WriteLine();*/

        return neighbours;
    }

}