2022-10-05：在一个 n x n 的整数矩阵 grid 中，
每一个方格的值 gridi 表示位置 (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(N*2logN)。
空间复杂度：O(N**2)。
代码用rust编写。代码如下：
代码语言：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
}
}执行结果如下：
在这里插入图片描述左神java代码
