2022-04-19£ºA*Ëã·¨, ¹ý³ÌºÍDijskra¸ß¶ÈÏà´¦, Óе½ÖÕµãµÄÔ¤¹Àº¯Êý, Ö»ÒªÔ¤¹ÀÖµ£¼=¿Í¹ÛÉÏ×îÓžàÀ룬¾ÍÊǶԵġ£ Ô¤¹Àº¯ÊýÊÇÒ»ÖÖÎüÒýÁ¦£º 1£©ºÏ

use rand::Rng;
fn main() {
    let mut map: Vec<Vec<isize>> = vec![];
    for i in 0..10 {
        map.push(vec![]);
        for j in 0..10 {
            map[i].push(0);
        }
    }
    for i in 0..map.len() {
        for j in 0..map[0].len() {
            map[i][j] = rand::thread_rng().gen_range(1, 10);
        }
    }
    let startX: isize = 0;
    let startY: isize = 0;
    let targetX: isize = 4;
    let targetY: isize = 7;
    let ret: isize = min_distance2(&mut map, startX, startY, targetX, targetY);
    for i in 0..10 {
        println!("{:?}", map[i]);
    }
    println!("{}", ret);
}

const MAX_VALUE: isize = 9223372036854775807;

fn min_distance2(
    map: &mut Vec<Vec<isize>>,
    startX: isize,
    startY: isize,
    targetX: isize,
    targetY: isize,
) -> isize {
    if map[startX as usize][startY as usize] == 0 || map[targetX as usize][targetY as usize] == 0 {
        return MAX_VALUE;
    }
    let n = map.len() as isize;
    let m = map[0].len() as isize;
    let mut heap: Vec<Vec<isize>> = Vec::new();
    let mut closed: Vec<Vec<bool>> = Vec::new();
    for i in 0..n {
        closed.push(Vec::new());
        for j in 0..m {
            closed[i as usize].push(false);
        }
    }
    let mut t = vec![
        map[startX as usize][startY as usize],
        distance(startX, startY, targetX, targetY),
        startX,
        startY,
    ];
    heap.push(t);
    let mut ans = MAX_VALUE;
    while heap.len() > 0 {
        //ÓÃÇÐƬģÄâ¶Ñ£¬ËùÒÔÐèÒªÅÅÐò
        heap.sort_by(|x, y| (x[0] + x[1]).cmp(&(y[0] + y[1])));

        // ±¨´í
        // let mut cur: &Vec<isize> = &(heap[0]);
        // heap.remove(0);

        let mut fromDistance: isize = heap[0][0];
        let mut row: isize = heap[0][2];
        let mut col: isize = heap[0][3];
        heap.remove(0); //±ØÐë·ÅÔÚÕâÀï
        if (closed[row as usize][col as usize]) {
            continue;
        }
        closed[row as usize][col as usize] = true;
        if (row == targetX && col == targetY) {
            ans = fromDistance;
            break;
        }
        add2(
            fromDistance,
            row - 1,
            col,
            targetX,
            targetY,
            n,
            m,
            map,
            &mut closed,
            &mut heap,
        );
        add2(
            fromDistance,
            row + 1,
            col,
            targetX,
            targetY,
            n,
            m,
            map,
            &mut closed,
            &mut heap,
        );
        add2(
            fromDistance,
            row,
            col - 1,
            targetX,
            targetY,
            n,
            m,
            map,
            &mut closed,
            &mut heap,
        );
        add2(
            fromDistance,
            row,
            col + 1,
            targetX,
            targetY,
            n,
            m,
            map,
            &mut closed,
            &mut heap,
        );
    }
    return ans;
}

fn add2(
    pre: isize,
    row: isize,
    col: isize,
    targetX: isize,
    targetY: isize,
    n: isize,
    m: isize,
    map: &mut Vec<Vec<isize>>,
    closed: &mut Vec<Vec<bool>>,
    heap: &mut Vec<Vec<isize>>,
) {
    if (row >= 0
        && row < n
        && col >= 0
        && col < m
        && map[row as usize][col as usize] != 0
        && !closed[row as usize][col as usize])
    {
        let mut t = vec![
            pre + map[row as usize][col as usize],
            distance(row, col, targetX, targetY),
            row,
            col,
        ];
        heap.push(t);
    }
}

// Âü¹þ¶Ù¾àÀë
fn distance(curX: isize, curY: isize, targetX: isize, targetY: isize) -> isize {
    return abs(targetX - curX) + abs(targetY - curY);
}

fn abs(a: isize) -> isize {
    if a < 0 {
        -a
    } else {
        a
    }
}