《leetcode刷题》-864-获取所有钥匙的最短路径-困难

题目

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

• $'.'代表一个空房间
• '#'代表一堵墙
• '@'代表起点
• 小写字母代表钥匙
• 大写字母代表锁

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

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

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

---

实例

提示：

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

---

思路

网格中的最短路径，一般能联想到的就是$BFS$

以普通的$BFS$不同，该题的$BFS$是可以走回头路的，即同一个网格可能会经过多次。

那么，如何进行$BFS$呢？
所有首先要明确经过某个网格都带有明确目的：去拿另一钥匙
其次要明白为什么会走回头路，走回头路的原因是必须先拿$X$钥匙，再去拿$Y$钥匙。

如上图，先去拿银色钥匙再去拿橙色钥匙，会重复走坐标为$(0,2)$这个网格。

仔细观察，经过$(0,2)$的两次所携带的钥匙状态是不一样的，因为走回头路的前提是已经拿到了钥匙，然后准备去拿下一个钥匙。

所以网格是可以重复经过的，但是每次经过时身上所携带的钥匙情况是不一样的。所有$BFS$可以这样遍历：

• 对于当前位置，可以走上下左右四个方向。
• 走动的前提是，该网格在当前携带钥匙的状态下之前没有经过这个格子。【使用$vis[m][n][2^K]$来表示遍历状态，$2^K$表示$K$把钥匙，最多$2^K$种状态】
• 对于每个网格，可以使用三元组$<x,y,state>$来表示；$x,y$表示网格位置，$state$表示状态。

对于携带钥匙的状态，可以使用状态压缩；最多6把钥匙，所以6个二进制数即可表示所有状态。

如：
$$state=001000$$
表示第三把钥匙已经拿到了，其他的没有拿到。

当KaTeX parse error: Expected 'EOF', got '&' at position 12: ((state>>k)&̲1)==1，表示第$k$把钥匙拿到手。

当$state==111111$，表示钥匙全部到手。即$state==((1<<ke{y}_{n}um)-1)$时。

代码

class Solution {
	public int shortestPathAllKeys(String[] grid) {
		int dir[] = {1,0,-1,0,1};//方向数组
        int m = grid.length,n=grid[0].length();//网格长宽
        int key_num = 0;//钥匙数量
        Queue <int[]>q = new LinkedList<int[]>();//用队列存储下一步遍历到的网格
        for(int i = 0;i<m;i++){//循环找到起点坐标，并统计钥匙数量
            for(int j=0;j<n;j++){
            	char c = grid[i].charAt(j);
                if(c=='@'){
                    q.add(new int[]{i,j,0});
                }else if(c>='a'&&c<='f') {
                	key_num++;
                }
            }
        }
        boolean[][][] vis = new boolean[m][n][1<<key_num];//遍历状态数组
        
        int ans = 0;
        while(!q.isEmpty()) {//当队列中还存在需要BFS的网格，一次while循环就是对队列中的网格进行一次四个方向的遍历
        	int cycle = q.size();
        	for(int t=0;t<cycle;t++) {//对队列中的网格依次进行四个方向的遍历
        		int point[] = q.poll();
        		if(point[2]==(1<<key_num)-1)return ans;//钥匙全部拿到，返回步数
            	for(int i=0;i<4;i++) {//上下左右四个方向进行遍历
            		int x = point[0]+dir[i];
            		int y = point[1]+dir[i+1];
            		int state = point[2];
            		if(x>=0&&x<m&&y>=0&&y<n) {
            			char c = grid[x].charAt(y);
            			if(c=='#') {//是一堵墙，跳过
            				continue;
            			}else if((c=='.'||c=='@')&&!vis[x][y][state]) {//是起点和空房间，当前状态没遍历过，移动到该网格，即入队列
            				q.add(new int[]{x,y,state});
            				vis[x][y][state] = true;
            			}else if(c<='f'&&c>='a') {//是钥匙，判断是否已经拿过。没拿过则拿钥匙并改变状态
            				int now_state = state|(1<<c-'a');
            				if(!vis[x][y][now_state]) {
            					q.add(new int[]{x,y,now_state});
                				vis[x][y][state] = true;
            				}
            			}else {//是锁头。判断是否当前状态是否来过和是否拿到该锁头的钥匙
            				if(!vis[x][y][state]&&((state>>(c-'A'))&1)==1) {
            						q.add(new int[]{x,y,state});
            						vis[x][y][state] = true;
            						
            				}
            			}
            		}
            	}
        	}
        	ans++;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56