How about printing the path that leads to open the lock


  • 0
    D
            private static List<string> PrintPath(string[] deadends, string target)
            {
                List<string> path = new List<string>();
                if (string.IsNullOrEmpty(target) || target.Length != 4) return path;
                string initialPosition = "0000";
                if (target == initialPosition) return path;
                //todo: check that each char in target is between 0-9
                HashSet<string> dds = new HashSet<string>(deadends);
                HashSet<string> visited = new HashSet<string>();
                Queue<LockCombination> queue = new Queue<LockCombination>();
                if (deadends.Contains(target) || deadends.Contains(initialPosition)) return path;
                queue.Enqueue(new LockCombination { value = initialPosition});
                visited.Add(initialPosition);
                while (queue.Count > 0)
                {
                    int queueItemCount = queue.Count;
                    for (int i = 0; i < queueItemCount; ++i)
                    {
                        LockCombination t = queue.Dequeue();
                        List<string> nextmoves = GetNextPossibleMoves(t.value);
                        foreach (string nextmove in nextmoves)
                        {
                            if (nextmove == target)
                            {
                                t.path.Add(target);
                                return t.path;
                            }
                            if (visited.Contains(nextmove)) continue;
                            if (dds.Contains(nextmove)) continue;
                            List<string> nextPath = new List<string>(t.path);
                            nextPath.Add(t.value);
                            queue.Enqueue(new LockCombination {
                                value = nextmove,
                                path = nextPath                       
                            });
                            visited.Add(nextmove);
                        }
                    }
                }
                return path;
            }
    
            private static List<string> GetNextPossibleMoves(string start)
            {
                List<string> nextMoves = new List<string>();
                for(int i = 0; i < 4; ++i)
                {
                    // for each position we can go upward and downword
                    char[] charArray = start.ToArray();
                    charArray[i] = Convert.ToChar((charArray[i] - '0' + 1) % 10 + '0');
                    nextMoves.Add(new string(charArray));
    
                    charArray = start.ToCharArray();
                    charArray[i] = Convert.ToChar((charArray[i] - '0' - 1 + 10) % 10 + '0');
                    nextMoves.Add(new string(charArray));
                }
                return nextMoves;
            }
        class LockCombination
        {
            public string value = null;
            public List<string> path = new List<string>();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.