public class Solution {

    public int OpenLock(string[] deadends, string target) {

        int[] distances = Enumerable.Repeat(int.MaxValue, 10000).ToArray();

        distances[0] = 0;

        foreach (string deads in deadends) {

            int dead = int.Parse(deads);

            distances[dead] = -1;

            if (dead == 0) {

                return -1;

            }

        }

        Queue<int> queue = new Queue<int>();

        queue.Enqueue(0);

        while (queue.Count > 0) {

            int current = queue.Dequeue();

            int distance = distances[current];

            foreach (int neighbour in GetNeighbours(current)) {

                if (distances[neighbour] > distance + 1) {

                    distances[neighbour] = distance + 1;

                    queue.Enqueue(neighbour);

                }

            }

        }

        int tint = int.Parse(target);

        if (distances[tint] == int.MaxValue) {

            distances[tint] = -1;

        }

        return distances[tint];

    }

    public int[] GetNeighbours(int num) {

        int a = (num % 10000) / 1000;

        int b = (num % 1000) / 100;

        int c = (num % 100) / 10;

        int d = (num % 10) / 1;

        return new[] {

            1000 * a + 100 * b + 10 * c + 1 * ((d + 9) % 10),

            1000 * a + 100 * b + 10 * c + 1 * ((d + 1) % 10),

            1000 * a + 100 * b + 10 * ((c + 9) % 10) + 1 * d,

            1000 * a + 100 * b + 10 * ((c + 1) % 10) + 1 * d,

            1000 * a + 100 * ((b + 9) % 10) + 10 * c + 1 * d,

            1000 * a + 100 * ((b + 1) % 10) + 10 * c + 1 * d,

            1000 * ((a + 9) % 10) + 100 * b + 10 * c + 1 * d,

            1000 * ((a + 1) % 10) + 100 * b + 10 * c + 1 * d,

        };

    }

}