Today I want to introduce my variant of solution for Shortest Path to Get All Keys problem, which is based on another implementation. So, here are my improvements.
  Algorithm is based on BFS(Breadth-First-Search). It uses PathState instance for keeping actual traversal state.
  The main trouble with the original implementation was that although it works pretty well, it’s impossible to track the whole path step-by-step, which makes understanding logic very difficult.   Besides cosmetic syntax changes related to migrating code to Kotlin, I’ve made 3 logic updates:

  • val moves: LinkedList<Pair<Int, Int>>
      As mentioned, original implementation didn’t have a mechanism of tracking path step by step, so in some complex scenarios like getPathTest_4keys_free_ride_center it were cases when some piece of path was not included and therefore total amount of steps was wrong. This fix provides exact chain of steps, e.g. for any scenario it’s possible to track traversing logic.
  • private var centralKeyStore: Set<Char> = mutableSetOf()
      This element is needed for keeping all found keys in one place, so that they were not distributed in different PathState instances during traversal.
  • queue.clear()
      val queue = ArrayDeque<PathState>() is the main element in BFS. In this particular task there were cases, when key was found, but because of other PathState instances in queue, traversing was continued from another cell, which is, obviously, wrong. Clearing queue after finding a key and adding it to centralKeyStore fixes this issue.

  Overall time complexity will be O(n x m), where n & m - size of grid.
  Although “shortest path” is stated in title, I think that in many cases this approach won’t find the shortest path, because this algorithm works in greedy manner, that means that in some cases there can be more with less amount of steps. So, for more optimal way we need to scan the whole grid and use something similar to Bellman-Ford algorithm, which make several traversals, each time getting closer to optimal solution.

  Hope, it was interesting and helpful, test cases are here. See you! :-)