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
    }
}