LC-864.获取所有钥匙的最短路径

题目描述

leetcode 困难题

给定一个二维网格 grid ，其中：

• ‘.’ 代表一个空房间
• ‘#’ 代表一堵
• ‘@’ 是起点
• 小写字母代表钥匙
• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例1：

输入：grid = ["@.a.#","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。

示例2：

输入：grid = ["@..aA","..B#.","....b"]
输出：6

示例3：

输入: grid = ["@Aa"]
输出: -1

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'
钥匙的数目范围是 [1, 6] 
每个钥匙都对应一个 不同 的字母
每个钥匙正好打开一个对应的锁

BFS + 状态压缩

对于最短路径我们可以通过 BFS 求出，并且因为钥匙最多只有 6 把，所以可以通过一个 int 来记录当前路径获得钥匙的情况 (称为 state)，对应位数为 1 时代表已经取得对应钥匙。

需要注意的是，不同于普通的 BFS：在确定访问状态时，不能仅仅通过坐标 x, y 来确定，还要加入状态，也就是说通过 x, y, state 来确定一个访问状态。

这是因为比如说经过某个房间 a 后，在房间 b 拿到一把新锁，接着又因为碰到墙壁或者其他未拿到钥匙的锁需要原路返回，重新经过了 a，那么这显然是一条新的有效路径（因为拿到了 b 的锁），所以我们还需要加入钥匙 state 来确定访问状态。反之如果坐标和钥匙 state 都相同，就是无效的路径，无需重新入队。

class Solution {
    static int[][] help = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int shortestPathAllKeys(String[] grid) {
        int n = grid.length;
        int m = grid[0].length();
        int keyCount = 0;
        char[][] g = new char[n][];
        int stratx = 0, starty = 0;
        // 初始化图、统计钥匙数量、记录起点
        for(int i = 0; i < n; i++){
            g[i] = new char[m];
            for(int j = 0; j < m; j++){
                char c = grid[i].charAt(j);
                g[i][j] = c;
                int sub = c - 'a';
                if(0 <= sub && sub <= 23){
                    keyCount++;
                }
                if(c == '@'){
                    stratx = i;
                    starty = j;
                }
            }
        }
        // Deque for BFS
        Deque<int[]> deque = new ArrayDeque<>();
        deque.offerLast(new int[]{stratx, starty, 0});
        // 通过 `[x][y][state]` 来确定访问状态，并且记录下此时的路径距离，初始化为 -1 表示未访问过
        int[][][] vis = new int[n][m][1 << keyCount];
        IntStream.range(0, n).forEach(i -> IntStream.range(0, m).forEach(j -> Arrays.fill(vis[i][j], - 1)));
        vis[stratx][starty][0] = 0;
        while(!deque.isEmpty()){
            int[] cur = deque.pollFirst();
            int d = vis[cur[0]][cur[1]][cur[2]] + 1;
            for(int i = 0; i < help.length; i++){
                int x = cur[0] + help[i][0];
                int y = cur[1] + help[i][1];
                if(!checkIndex(x, y, n, m) || g[x][y] == '#'){
                    continue;
                }
                char c = g[x][y];
                int state = cur[2];
                if(c != '.' && c != '@' && (c & 32) == 0){
                    // 锁
                    int need = 1 << (c - 'A');
                    if((state & need) != need){
                        continue;
                    }
                }
                if(c != '.' && (c & 32) == 32){ 
                    // 钥匙
                    state |= (1 << (c - 'a'));
                    if(getCurKeyCount(state) == keyCount){
                        return d;
                    }
                }
                if(vis[x][y][state] == -1){
                    vis[x][y][state] = d;
                    deque.offer(new int[]{x, y, state});
                }
            }
        }
        return -1;
    }

    private boolean checkIndex(int x, int y, int xLimit, int yLimit){
        return x >= 0 && y >= 0 && x < xLimit && y < yLimit;
    }

    private int getCurKeyCount(int state){
        int count = 0;
        while(state > 0){
            if((state & 1) == 1){
                count++;
            }
            state = state >> 1;
        }
        return count;
    }
}