864 Shortest Path to Get All Keys

864. Shortest Path to Get All Keys

1. Question

We are given a 2-dimensional grid. "."is an empty cell,"#"is a wall,"@"is the starting point, ("a","b", ...) are keys, and ("A", "B", ...) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can't walk over a lock unless we have the corresponding key.

For some1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the firstKletters 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's impossible, return-1.

Example 1:

Input: ["@.a.#","###.#","b.A.B"]
Output: 8

Example 2:

Input: ["@..aA","..B#.","....b"]
Output: 6

Note:

1. 1 <= grid.length <= 30

2. 1 <= grid[0].length <= 30

3. grid[i][j]contains only'.','#','@', 'a'-'f'and'A'-'F'

4. The number of keys is in[1, 6]. Each key has a different letter and opens exactly one lock.

2. Implementation

(1) BFS

思路:

(1) 这题的状态由三部分组成: x, y, 当前拥有的key，因为题目指出行列的数目在[1, 30]之间，2^8 = 256 > 30, 我们可以用24位的bit表示这三部分。具体的做法是bit的前8位表示x，中间8位表示y，最后8位表示拥有的key。比如，假设我们当前(3, 4)位置，x = 3, y = 4, 拥有的key是{a, b, e}, 则状态表示为 (3 << 16 | 4 << 8 | 10011)

(2) 首先，我们要先遍历整个grid，找出初始状态(起始位置和key = 0的时候)，同时找出key的数量

(3) 然后就是用BFS，找出最短路径了

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length, n = grid[0].length();
        int allKeys = 0;

        Queue<Integer> queue = new LinkedList();
        int[][][] visited = new int[m][n][64];

        // Find the initial state and the number of keys
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);

                if (c == '@') {
                    queue.add((i << 16) | (j << 8));
                    visited[i][j][0] = 1;
                }
                else if (c >= 'a' && c <= 'f') {
                    allKeys |= (1 << (c - 'a'));
                }
            }
        }

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int curState = queue.remove();
                int row = curState >> 16;
                int col = ((curState >> 8) & 0xff);
                int keys = curState & 0xff;

                // Found all the keys
                if (keys == allKeys) {
                    return steps;
                }

                for (int [] direction : directions) {
                    int nextRow = row + direction[0];
                    int nextCol = col + direction[1];
                    int nextKeys = keys;

                    if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) continue;

                    char c = grid[nextRow].charAt(nextCol);

                    // Wall
                    if (c == '#') continue;

                    // Don't have the key to open the door
                    if (c >= 'A' && c <= 'F' && (nextKeys & (1 << (c - 'a'))) == 0) continue;

                    // Visited state
                    if (visited[nextRow][nextCol][nextKeys] == 1) continue;

                    // Update key
                    if (c >= 'a' && c <= 'f') {
                        nextKeys |= (1 << (c - 'a'));
                    }
                    queue.add((nextRow << 16) | (nextCol << 8) | nextKeys);
                    visited[nextRow][nextCol][nextKeys] = 1;
                }
            }
            ++steps;
        }
        return -1;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(m * n * 2 ^ k), m是grid的行，n是grid的列，k是keys的数量