864. Shortest Path to Get All Keys

leetcode_864.md

Description

You are given an m x n grid 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.

Link to the original problem

Example 1:

Input: grid = ["@.a.#","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] is either an English letter, '.', '#', or '@'.
• The number of keys in the grid is in the range [1, 6].
• Each key in the grid is unique.
• Each key in the grid has a matching lock.

Idea

1. Honestly, when I first finish reading this question, I immediately sense that this is not an easy one and I don't know what to do.
2. So I did a quick search and found this post. I found the code is clean and organized so I referenced his/her idea here. I did update the code a bit because it is in TypeScript, also I renamed a few variables to make it easier to understand.
3. OK, let's get back to business.
4. If you follow the pattern for the shortest path series, you would probably also realize that we can use the good old BFS to find the shortest path, because we still need to move forward in the grid to grab all the keys.
5. However, this time we need to collect keys before we can open the corresponding locks. Hmm, there could be so many ways that we can collect the keys and traverse the grid. Oh my, I'm not sure what to do now.
6. OK, let's not panick here, because once you calm down, good things happen! :)
7. First, you'll notice that we can have maximum 6 keys. So if we brute force all different orders in which we can collect the keys (!6 (=720) of them, so not too many), can we find some basic solution?
8. Suppose it would work, what do we do? We have to try the orders one by one and check if the order is possible and then find the shortest path to collect the keys following the order? It doesn't sound about right.
9. So what is the key problem here?
10. After some thinking, I notice the problem is that, when we follow a path and collect keys and run into a lock, we need to know if we have the key for it. If we have it, we can move on. If not, then it's blocked. So we need to remember this information somehow.
11. So how do we (efficiently) remember this?
12. For example, we can use an array keys of size 6 to mark if we have a particular key or not, like arr[0] = 0 means we don't have key a, and arr[0] = 1 means we have key a.
13. At this momemnt, some readers might say, "hey, if we are only recording a state of on and off, we can just use one bit for it and save some space?" Exactly, you guys are smart!
14. So basically we can use a bit mask for each key and it would work exactly the same, like 000010 (binary) meaning we have key `b.
15. OK, let's revisit what we have now, so we know we need BFS to move forward, and we have bit masks to remember if we have a certain key. What's still missing?
16. We can define our "state" now, which can be [current row, current col, current steps, current keys].
17. Also we need to know when we get to a certain cell in the grid, do we already have a shorter path with same keys? If yes, we don't need to revisit it, because current path won't be shorter.
18. In that case, we need a 3D array of shape (rows, cols, 1 << 6) (6 is because we have maximum 6 keys).
19. At last I want to emphasize that the helpers functions in the original post I referenced are small but powerful, really clean and clear code!
20. Also state compression is a really cool trick you'll find useful sometimes. So let's remember that!
21. Now the code should explain itself.

Solution

Javascript

const shortestPathAllKeys = grid => {
  const DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  const R = grid.length, C = grid[0].length;

  const inRange = (r, c) => r >= 0 && r < R && c >= 0 && c < C;
  const isStart = ch => ch == '@';
  const isWall = ch => ch == '#';
  const isKey = ch => /[a-z]/.test(ch);
  const isLock = ch => /[A-Z]/.test(ch);
  const keyIdx = k => k.charCodeAt(0) - 'a'.charCodeAt(0);
  const addKey = (keys, k) => keys | (1 << keyIdx(k));
  const hasKey = (keys, k) => (keys & (1 << keyIdx(k))) !== 0;
  const keyOf = lock => lock.toLowerCase();
  const dist = Array(R).fill(0).map(_ => Array(C).fill(0).map(_ => Array(1 << 6).fill(Infinity)));

  const queue = []; // state is [row, col, steps, keys]
  let targetKeys = 0;
  for (let r = 0; r < R; r += 1) {
    for (let c = 0; c < C; c += 1) {
      const ch = grid[r][c];
      if (isStart(ch)) {
        queue.push([r, c, 0, 0]); // adding start point
        dist[r][c][0] = 0;
      } else if (isKey(ch)) {
        targetKeys = addKey(targetKeys, ch); // collect target keys
      }
    }
  }
  while (queue.length) {
    const [r, c, step, keys] = queue.shift();
    if (keys == targetKeys) return step;
    for (const [dr, dc] of DIRS) {
      const [nr, nc] = [r + dr, c + dc];
      if (!inRange(nr, nc)) continue;
      const ch = grid[nr][nc];
      if (isWall(ch)) continue;
      if (isLock(ch) && !hasKey(keys, keyOf(ch))) continue;
      const nk = isKey(ch) ? addKey(keys, ch) : keys;
      if (step + 1 < dist[nr][nc][nk]) {
        dist[nr][nc][nk] = step + 1;
        queue.push([nr, nc, step + 1, nk]);
      }
    }
  }
  return -1;
}

References

1. BFS + state comprehension
2. Leetcode 1730
3. Leetcode 1091
4. Leetcode 1293