LeetCode_BFS_困难_864.获取所有钥匙的最短路径

客官°小女子只卖身不卖艺 2023-10-07 21:05 5阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

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

**示例 1：**  
![在这里插入图片描述][ccf6450bb6ee4a09a4708015e7841b19.png]  
输入：grid = \[“@.a.\#”,“\#\#\#.\#”,“b.A.B”\]  
输出：8  
解释：目标是获得所有钥匙，而不是打开所有锁。

**示例 2：**  
![在这里插入图片描述][8f725ba9200246baa8fbc8e074166c48.png]  
输入：grid = \[“@…aA”,“…B\#.”,“…b”\]  
输出：6

**示例 3：**  
![在这里插入图片描述][c74be34036274fe3836e011b0ea93776.png]  
输入: grid = \[“@Aa”\]  
输出: -1

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys

## 2.思路 ##

（1）BFS & 位运算  
思路参考[本题官方题解][Link 1]，具体细节见下方代码中的注释。

## 3.代码实现（Java） ##

//思路1————BFS & 位运算
    class Solution {
        
        
        //定义遍历的四个方向
        static int[][] dirs = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
    
        public int shortestPathAllKeys(String[] grid) {
        
            int m = grid.length;
            int n = grid[0].length();
            // (startX, startY) 用于记录起点坐标
            int startX = 0;
            int startY = 0;
            // keyToIndex 保存表示钥匙的字母及其对应的序号
            Map<Character, Integer> keyToIndex = new HashMap<>();
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    char c = grid[i].charAt(j);
                    if (c == '@') {
        
                        //记录起点坐标
                        startX = i;
                        startY = j;
                    } else if (Character.isLowerCase(c)) {
        
                        if (!keyToIndex.containsKey(c)) {
        
                            //表示钥匙的字母及其对应的序号
                            int idx = keyToIndex.size();
                            keyToIndex.put(c, idx);
                        }
                    }
                }
            }
            /*
                用三元组 (x, y, mask) 来表示当前的状态，其中：
                (1) (x, y) 表示当前所处的位置坐标
                (2) mask 是一个二进制数，其长度等于网格中钥匙的数目，mask 的第 i 个二进制位为 1，
                    当且仅当我们已经获得了网格中的第 i 把钥匙
            */
            int[][][] dist = new int[m][n][1 << keyToIndex.size()];
            //初始化 dist
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    Arrays.fill(dist[i][j], -1);
                }
            }
            //使用 BFS 所需要用到的队列
            Queue<int[]> queue = new ArrayDeque<>();    
            //将起点加入到队列中
            queue.offer(new int[]{
        startX, startY, 0});
            dist[startX][startY][0] = 0;
            while (!queue.isEmpty()) {
        
                int[] arr = queue.poll();
                int x = arr[0];
                int y = arr[1];
                int mask = arr[2];
                //分别朝四个方向进行遍历
                for (int i = 0; i < 4; i++) {
        
                    int nextX = x + dirs[i][0];
                    int nextY = y + dirs[i][1];
                    //判断是否出界，以及是否遇到堵
                    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX].charAt(nextY) != '#') {
        
                        char c = grid[nextX].charAt(nextY);
                        if (c == '.' || c == '@') {
        
                            //遇到空房间或起点
                            if (dist[nextX][nextY][mask] == -1) {
        
                                dist[nextX][nextY][mask] = dist[x][y][mask] + 1;
                                queue.offer(new int[]{
        nextX, nextY, mask});
                            }
                        } else if (Character.isLowerCase(c)) {
        
                            //遇到钥匙
                            int idx = keyToIndex.get(c);
                            if (dist[nextX][nextY][mask | (1 << idx)] == -1) {
        
                                dist[nextX][nextY][mask | (1 << idx)] = dist[x][y][mask] + 1;
                                if ((mask | (1 << idx)) == (1 << keyToIndex.size()) - 1) {
        
                                	//已获取到所有的钥匙
                                    return dist[nextX][nextY][mask | 1 << idx];
                                }
                                queue.offer(new int[]{
        nextX, nextY, mask | (1 << idx)});
                            }
                        } else {
        
                            //遇到锁
                            int idx = keyToIndex.get(Character.toLowerCase(c));
                            /* 
                                (mask & (1 << idx)) != 0 说明此时手中拥有可以打开当前锁的钥匙
                                dist[nextX][nextY][mask] == -1 说明 (nextX, nextY) 还未被遍历过
                            */
                            if ((mask & (1 << idx)) != 0 && dist[nextX][nextY][mask] == -1) {
        
                                dist[nextX][nextY][mask] = dist[x][y][mask] + 1;
                                queue.offer(new int[]{
        nextX, nextY, mask});
                            }
                        }
                    }
                }
            }
            //无法获取所有钥匙，返回 -1
            return -1;
        }
    }

[ccf6450bb6ee4a09a4708015e7841b19.png]: https://img-blog.csdnimg.cn/ccf6450bb6ee4a09a4708015e7841b19.png
[8f725ba9200246baa8fbc8e074166c48.png]: https://img-blog.csdnimg.cn/8f725ba9200246baa8fbc8e074166c48.png
[c74be34036274fe3836e011b0ea93776.png]: https://img-blog.csdnimg.cn/c74be34036274fe3836e011b0ea93776.png
[Link 1]: https://leetcode.cn/problems/shortest-path-to-get-all-keys/solution/huo-qu-suo-you-yao-chi-de-zui-duan-lu-ji-uu5m/