Solution


Approach 1: Brute Force + Permutations

Intuition and Algorithm

We have to pick up the keys in some order, say .

For each ordering, let's do a breadth first search to find the distance to the next key.

For example, if the keys are 'abcdef', then for each ordering such as 'bafedc', we will try to calculate the candidate distance from '@' -> 'b' -> 'a' -> 'f' -> 'e' -> 'd' -> 'c'.

Between each segment of our path (and corresponding breadth-first search), we should remember what keys we've picked up. Keys that are picked up become part of a mask that helps us identify what locks we are allowed to walk through during the next breadth-first search.

Each part of the algorithm is relatively straightforward, but the implementation in total can be quite challenging. See the comments for more details.

Complexity Analysis

  • Time Complexity: , where are the dimensions of the grid, and is the maximum number of keys ( because it is the "size of the alphabet".) Each bfs is performed up to times.

  • Space Complexity: , the space for the bfs and to store the candidate key permutations.


Approach 2: Points of Interest + Dijkstra

Intuition and Algorithm

Clearly, we only really care about walking between points of interest: the keys, locks, and starting position. We can use this insight to speed up our calculation.

Let's make this intuition more formal: any walk can be decomposed into primitive segments, where each segment (between two points of interest) is primitive if and only if it doesn't touch any other point of interest in between.

Then, we can calculate the distance (of a primitive segment) between any two points of interest, using a breadth first search.

Afterwards, we have some graph (where each node refers to at most places, and at most states of keys). We have a starting node (at '@' with no keys) and ending nodes (at anywhere with all keys.) We also know all the costs to go from one node to another - each node has outdegree at most 13. This shortest path problem is now ideal for using Dijkstra's algorithm.

Dijkstra's algorithm uses a priority queue to continually searches the path with the lowest cost to destination, so that when we reach the target, we know it must have been through the lowest cost path. Refer to this link for more detail.

Again, each part of the algorithm is relatively straightforward (for those familiar with BFS and Dijkstra's algorithm), but the implementation in total can be quite challenging.

Complexity Analysis

  • Time Complexity: , where are the dimensions of the grid, and is the maximum number of keys, is the number of nodes when we perform Dijkstra's, and is the maximum number of edges.

  • Space Complexity: .


Analysis written by: @awice.