2023-03-06：给定一个二维网格 grid ，其中：
'.' 代表一个空房间
'#' 代表一堵
'@' 是起点
小写字母代表钥匙
大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
我们不能在网格外面行走，也无法穿过一堵墙
如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
输入：grid = ["@.a.#","###.#","b.A.B"]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。
来自Airbnb、Uber。
答案2023-03-06：
dijkstra算法。
代码用rust编写。代码如下：
代码语言：javascript复制use std::iter::repeat;
fn main() {
let mut grid = vec!["@.a.#", "###.#", "b.A.B"];
let ans = shortestPathAllKeys(&mut grid);
println!("ans = {}", ans);
}
// "@....#"
// "..b..B"
//
// @ . . . . #
// . . B . . B
fn shortestPathAllKeys(grid: &mut Vec<&str>) -> i32 {
let n = grid.len() as i32;
let mut map: Vec<Vec<u8>> = repeat(vec![]).take(n as usize).collect();
for i in 0..grid.len() {
map[i as usize] = grid[i as usize].as_bytes().to_vec();
}
let m = map[0].len() as i32;
return dijkstra(&mut map, n, m);
}
fn dijkstra(map: &mut Vec<Vec<u8>>, n: i32, m: i32) -> i32 {
let mut startX = 0;
let mut startY = 0;
let mut keys = 0;
for i in 0..n {
for j in 0..m {
if map[i as usize][j as usize] == '@' as u8 {
startX = i;
startY = j;
}
if map[i as usize][j as usize] >= 'a' as u8 && map[i as usize][j as usize] <= 'z' as u8
{
keys = 1;
}
}
}
// 如果有4把钥匙
// limit = 0000..00001111
// 如果有5把钥匙
// limit = 0000..00011111
// 也就是说，所有钥匙都凑齐的状态，就是limit
let mut limit = (1 << keys) - 1;
// 用堆来维持走过的点(dijkstra标准操作)
// 维持的信息是一个个小的4维数组，arr
// arr[0] : 当前来到的x坐标
// arr[1] : 当前来到的y坐标
// arr[2] : 当前收集到的钥匙状态
// arr[3] : 从出发点到当前的距离
// 堆根据距离的从小到大组织，距离小根堆
// PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[3] - b[3]);
let mut heap: Vec<Vec<i32>> = vec![];
let mut visited: Vec<Vec<Vec<bool>>> = repeat(
repeat(repeat(false).take(1 << keys).collect())
.take(m as usize)
.collect(),
)
.take(n as usize)
.collect();
// startX, startY, 000000
heap.push(vec![startX, startY, 0, 0]);
while heap.len() > 0 {
heap.sort_by(|a, b| a[3].cmp(&b[3]));
let cur = heap.pop().unwrap();
let x = cur[0];
let y = cur[1];
let s = cur[2];
let w = cur[3];
if s == limit {
return w;
}
if visited[x as usize][y as usize][s as usize] {
continue;
}
visited[x as usize][y as usize][s as usize] = true;
add(x - 1, y, s, w, n, m, map, &mut visited, &mut heap);
add(x 1, y, s, w, n, m, map, &mut visited, &mut heap);
add(x, y - 1, s, w, n, m, map, &mut visited, &mut heap);
add(x, y 1, s, w, n, m, map, &mut visited, &mut heap);
}
return -1;
}
// 当前是由(a,b,s) -> (x,y,状态？)
// w ，从最开始到达(a,b,s)这个点的距离 -> w 1
// n,m 固定参数，防止越界
// map 地图
// visited 访问过的点，不要再加入到堆里去！
// heap, 堆！
fn add(
x: i32,
y: i32,
mut s: i32,
w: i32,
n: i32,
m: i32,
map: &mut Vec<Vec<u8>>,
visited: &mut Vec<Vec<Vec<bool>>>,
heap: &mut Vec<Vec<i32>>,
) {
if x < 0 || x == n || y < 0 || y == m || map[x as usize][y as usize] == '#' as u8 {
return;
}
if map[x as usize][y as usize] >= 'A' as u8 && map[x as usize][y as usize] <= 'Z' as u8 {
// 锁！
// B -> 00000010
// dcba
// x,y,状 = x,y,s
// s == 00001000
// dcba
// A s & (1 << 0) != 0
// B s & (1 << 1) != 0
// D s & (1 << 3) != 0
//
if (!visited[x as usize][y as usize][s as usize]
&& (s & (1 << (map[x as usize][y as usize] - 'A' as u8))) != 0)
{
heap.push(vec![x, y, s, w 1]);
}
} else {
// 不是锁！
// 要么是钥匙 a b c
// 要么是空房间 .
// 要么是初始位置 @
if map[x as usize][y as usize] >= 'a' as u8 && map[x as usize][y as usize] <= 'z' as u8 {
s |= 1 << (map[x as usize][y as usize] - ('a' as u8)) as i32;
}
if !visited[x as usize][y as usize][s as usize] {
heap.push(vec![x, y, s, w 1]);
}
}
}
