题目分析

本题也是一个经典的小游戏了，不知道小伙伴们有没有玩过类似的游戏。在游戏中往往通关就可以，不需要找到最短的路径。

广度优先搜索

本题比普通题目困难在于路径是可以重复走的，因为要拿到所有的钥匙，所以可能拿到a钥匙，然后再去开A的锁，才能拿到b钥匙。因此我们要记录当前钥匙的状态。

因为钥匙数量为k，且k <= 6，所以可以用状态压缩的思想，使用二进制表示钥匙，第i位为1表示有第i把钥匙。

本题的两个要点：

要记录当前钥匙的状态，并用二进制表示。
visited数组的构造。

在常规的路径搜索题目中，visited数组是二维的，经过某个点就可以置为true。但是本题的重复路径不能用这个方法。但是如果不考虑visited，时间复杂度是 $O(4^{k \times (m + n)})$，因为极限情况下要把整张地图搜索k次，才能把k个钥匙搜索完成，每一次搜索要m + n步。这时显然TLE的。

所以visited数组是必须的，这应该如何构造呢？答案是根据钥匙的状态构造。钥匙的状态有2的k次方种。因此对于某一种情况，路径是不能重复的。比如已经有了第1，3把钥匙，此时路径(i, j)已经搜索过了，当再次遇到第1，3把钥匙，路径是(i, j)就可以不用继续搜索了。

算法的时间复杂度为O(2^k \times mn)，空间复杂度为O(2^k \times mn)。

class Solution {
    private int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int shortestPathAllKeys(String[] grid) {
        int row = grid.length;
        int col = grid[0].length();
        HashMap<Character, Integer> map = new HashMap<>();
        char[][] g = new char[row][col];
        Info start = new Info(0, 0, 0, 0);
        for (int i = 0; i < row; i++) {
            String s = grid[i];
            for (int j = 0; j < col; j++) {
                char c = s.charAt(j);
                g[i][j] = c;
                if (c >= 'a' && c <= 'z') {
                    map.put(c, map.size());
                } else if (c == '@') {
                    start = new Info(i, j, 0, 0);
                }
            }
        }
        int k = map.size();
        int cases = 1 << k;
        boolean[][][] visited = new boolean[row][col][cases];
        visited[start.row][start.col][0] = true;
        Queue<Info> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            Info cur = queue.poll();
            int newS = cur.step + 1;
            for (int[] direct : directions) {
                int newR = cur.row + direct[0];
                int newC = cur.col + direct[1];
                int newK = cur.key;
                if (0 <= newR && newR < row && 0 <= newC && newC < col) {
                    if (g[newR][newC] == '#') {
                        continue;
                    } else if (g[newR][newC] >= 'A' && g[newR][newC] <= 'Z') {
                        if ((cur.key & (1 << map.get((char) (g[newR][newC] + 32)))) == 0) {
                            continue;
                        }
                    } else if (g[newR][newC] >= 'a' && g[newR][newC] <= 'z') {
                        newK |= 1 << map.get(g[newR][newC]);
                        if (newK == cases - 1) {
                            return newS;
                        }
                    }
                    if (!visited[newR][newC][newK]) {
                        visited[newR][newC][newK] = true;
                        queue.add(new Info(newR, newC, newK, newS));
                    }
                }
            }
        }
        return -1;
    }

    private static class Info {
        int row;
        int col;
        int key;
        int step;

        Info (int row, int col, int key, int step) {
            this.row = row;
            this.col = col;
            this.key = key;
            this.step = step;
        }
    }
}

刷题总结

本题难度不小，抓住了两个要点，我要求小伙伴们能够写出本题。如果能顺利写出本题，那么搜索类的题目，基本上就不在话下了。