Problem Description
You are given an m x n grid where:
- '.' is an empty cell.
- '#' is a wall.
- '@' is the starting point.
- Lowercase letters represent keys.
- Uppercase letters represent locks.
You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall. If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.
For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys. If it is impossible, return -1.
Key Insights
- The problem can be represented as a graph where each cell is a node.
- Breadth-First Search (BFS) is suitable for finding the shortest path in an unweighted grid.
- Key-lock relationships enforce constraints on movement, requiring state management of collected keys.
- A bitmask can be used to efficiently track acquired keys.
Space and Time Complexity
Time Complexity: O(m * n * 2^k) where m and n are the grid dimensions and k is the number of keys.
Space Complexity: O(m * n * 2^k) for the visited state storage.
Solution
The solution employs a Breadth-First Search (BFS) algorithm to explore the grid. Each state in the BFS consists of the current position in the grid and the bitmask representing the keys that have been collected. The BFS explores all four possible movements (up, down, left, right) from the current cell. If a key is encountered, it is added to the bitmask, and if a lock is encountered, the algorithm checks if the corresponding key is held. The search continues until all keys are collected or all possible paths are exhausted.