2022-10-05：在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。当开始下雨时，在时间为 t 时，水池中的水位为 t 。

2022 年 10 月 05 日
北京
本文字数：1276 字
阅读完需：约 4 分钟

2022-10-05：在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。你从坐标方格的左上平台 (0，0) 出发。返回你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]。输出: 16。

答案 2022-10-05：

Dijkstra 算法。时间复杂度：O(N2*logN)。空间复杂度：O(N2)。

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

use std::iter::repeat;fn main() {    let mut grid = vec![        vec![0, 1, 2, 3, 4],        vec![24, 23, 22, 21, 5],        vec![12, 13, 14, 15, 16],        vec![11, 17, 18, 19, 20],        vec![10, 9, 8, 7, 6],    ];    let ans = swim_in_water2(&mut grid);    println!("ans = {}", ans);}
// Dijkstra算法fn swim_in_water2(grid: &mut Vec<Vec<i32>>) -> i32 {    let n = grid.len() as i32;    let m = grid[0].len() as i32;    let mut heap: Vec<Vec<i32>> = Vec::new();    let mut visited: Vec<Vec<bool>> = repeat(repeat(false).take(m as usize).collect())        .take(n as usize)        .collect();    heap.push(vec![0, 0, grid[0][0]]);    let mut ans = 0;    while heap.len() > 0 {        heap.sort_by(|a, b| a[2].cmp(&b[2]));        let r = heap[0][0];        let c = heap[0][1];        let v = heap[0][2];
        heap.remove(0);        if visited[r as usize][c as usize] {            continue;        }        visited[r as usize][c as usize] = true;        if r == n - 1 && c == m - 1 {            ans = v;            break;        }        add(grid, &mut heap, &mut visited, r - 1, c, v);        add(grid, &mut heap, &mut visited, r + 1, c, v);        add(grid, &mut heap, &mut visited, r, c - 1, v);        add(grid, &mut heap, &mut visited, r, c + 1, v);    }    return ans;}fn add(    grid: &mut Vec<Vec<i32>>,    heap: &mut Vec<Vec<i32>>,    visited: &mut Vec<Vec<bool>>,    r: i32,    c: i32,    pre_v: i32,) {    if r >= 0        && r < grid.len() as i32        && c >= 0        && c < grid[0].len() as i32        && !visited[r as usize][c as usize]    {        heap.push(vec![            r,            c,            pre_v + get_max(0, grid[r as usize][c as usize] - pre_v),        ]);    }}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}