2023-03-06：给定一个二维网格 grid ，其中： ‘.‘ 代表一个空房间 ‘#‘ 代表一堵 ‘@‘ 是起点 小写字母代表钥匙 大写字母代表锁 我们从起点开始出发，一次移动是指向四个基本方向之

2023-03-06：给定一个二维网格 grid ，其中：
‘.’ 代表一个空房间
‘#’ 代表一堵
‘@’ 是起点
小写字母代表钥匙
大写字母代表锁
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
我们不能在网格外面行走，也无法穿过一堵墙
如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
输入：grid = [“@.a.#”,“###.#”,“b.A.B”]
输出：8
解释：目标是获得所有钥匙，而不是打开所有锁。
来自Airbnb、Uber。

答案2023-03-06：

dijkstra算法。

代码用rust编写。代码如下：

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]);

        }

    }

}

2023-03-06：给定一个二维网格 grid ，其中： ‘.‘ 代表一个空房间 ‘#‘ 代表一堵 ‘@‘ 是起点 小写字母代表钥匙 大写字母代表锁 我们从起点开始出发，一次移动是指向四个基本方向之的相关教程结束。