2023-03-04：定义一个二维数组N*M，比如5*5数组下所示： 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,

use std::iter::repeat;
fn main() {
    let inputs = vec![
        5, 5, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0,
    ];
    let mut ii = 0;
    let n = inputs[ii];
    ii += 1;
    let m = inputs[ii];
    ii += 1;
    let mut map: Vec<Vec<i32>> = repeat(repeat(0).take(m as usize).collect())
        .take(n as usize)
        .collect();
    for i in 0..n {
        for j in 0..m {
            map[i as usize][j as usize] = inputs[ii];
            ii += 1;
        }
    }
    let mut ans = dijkstra(n, m, &mut map);
    ans.reverse();
    println!("{:?}", ans);
}

// n : n行
// m : m列
// map :
// 0 1 1 1
// 0 0 0 1
// 1 1 0 1
// 0 0 0 0
// list = [0,0] , [1,0], [1,1]...[3,3]
// [3,3] -> [0,0]
fn dijkstra(n: i32, m: i32, map: &mut Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    // (a,b) -> (c,d)
    // last[c][d][0] = a
    // last[c][d][1] = b
    // 从哪到的当前(c,d)
    let mut last: Vec<Vec<Vec<i32>>> = repeat(
        repeat(repeat(0).take(2).collect())
            .take(m as usize)
            .collect(),
    )
    .take(n as usize)
    .collect();

    // int[] arr = {c,d,w}
    //              0 1 距离
    //PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    let mut heap: Vec<Vec<i32>> = vec![];

    let mut visited: Vec<Vec<bool>> = repeat(repeat(false).take(m as usize).collect())
        .take(n as usize)
        .collect();
    heap.push(vec![0, 0, 0]);
    let mut ans: Vec<Vec<i32>> = vec![];
    while heap.len() > 0 {
        heap.sort_by(|a, b| a[2].cmp(&b[2]));
        let mut cur = heap.pop().unwrap();
        let x = cur[0];
        let y = cur[1];
        let w = cur[2];
        if x == n - 1 && y == m - 1 {
            break;
        }
        if visited[x as usize][y as usize] {
            continue;
        }
        // (x,y)这个点
        visited[x as usize][y as usize] = true;
        add(
            x,
            y,
            x - 1,
            y,
            w,
            n,
            m,
            map,
            &mut visited,
            &mut heap,
            &mut last,
        );
        add(
            x,
            y,
            x + 1,
            y,
            w,
            n,
            m,
            map,
            &mut visited,
            &mut heap,
            &mut last,
        );
        add(
            x,
            y,
            x,
            y - 1,
            w,
            n,
            m,
            map,
            &mut visited,
            &mut heap,
            &mut last,
        );
        add(
            x,
            y,
            x,
            y + 1,
            w,
            n,
            m,
            map,
            &mut visited,
            &mut heap,
            &mut last,
        );
    }
    let mut x = n - 1;
    let mut y = m - 1;
    while x != 0 || y != 0 {
        ans.push(vec![x, y]);
        let lastX = last[x as usize][y as usize][0];
        let lastY = last[x as usize][y as usize][1];
        x = lastX;
        y = lastY;
    }
    ans.push(vec![0, 0]);
    return ans;
}
// 当前是从(x,y) -> (i,j)
// 左上角 -> (x,y) , 距离是w
// 左上角 -> (x,y) -> (i,j) w+1
// 行一共有n行，0~n-1有效
// 列一共有m行，0~m-1有效
// map[i][j] == 1，不能走！是障碍！
// map[i][j] == 0，能走！是路！
// 把记录加入到堆里，所以得有heap
// last[i][j][0] = x
// last[i][j][1] = y
fn add(
    x: i32,
    y: i32,
    i: i32,
    j: i32,
    w: i32,
    n: i32,
    m: i32,
    map: &mut Vec<Vec<i32>>,
    visited: &mut Vec<Vec<bool>>,
    heap: &mut Vec<Vec<i32>>,
    last: &mut Vec<Vec<Vec<i32>>>,
) {
    if i >= 0
        && i < n
        && j >= 0
        && j < m
        && map[i as usize][j as usize] == 0
        && !visited[i as usize][j as usize]
    {
        heap.push(vec![i, j, w + 1]);
        last[i as usize][j as usize][0] = x;
        last[i as usize][j as usize][1] = y;
    }
}