题解 | 量子网络穿梭

参考 https://blog.nowcoder.net/n/14ee1a72165e41dab3fb88855f65fb64

use std::io::{self, BufRead};
use std::collections::BinaryHeap;
use std::cmp::Reverse;

// const DIRECTION: [(usize, usize); 4] = [()]

fn main() {
    let mut input = String::new();
    let stdin = io::stdin();
    let _ = stdin.lock().read_line(&mut input);
    let row: usize = input.trim().split(' ').nth(0).unwrap().parse().unwrap();
    input.clear();
    dbg!(row);
    let map: Vec<_> = (0..row).map(|_| {
        let mut input_2 = String::new();
        let _ = stdin.lock().read_line(&mut input_2);
        let v: Vec<char> = input_2.trim().to_lowercase().chars().collect();
        v
    }).collect();
    let col = map[0].len();

    // 初始化遍历
    let (gate, start, end) = {
        let mut gate: Vec<Vec<_>> = (0..row).map(|x| (0..col).map(|y| (x, y)).collect::<Vec<_>>()).collect();
        let mut gate_start: Option<(usize, usize)> = None;
        let mut start = (0, 0);
        let mut end = (0, 0);
        for i in 0..row {
            for j in 0..col {
                // dbg!(&gate);
                // dbg!(&start);
                match map[i][j] {
                    '2' => {
                        match gate_start.take() {
                            Some((x, y)) => {
                                gate[x][y] = (i, j);
                                gate[i][j] = (x, y);
                            },
                            None => {
                                gate_start = Some((i, j));
                            },
                        }
                    },
                    's' => {
                        start = (i, j);
                    },
                    'e' => {
                        end = (i, j);
                    },
                    '1' | '0' => (),
                    _ => unreachable!(),
                }
            }
        }
        (gate, start, end)
    };

    let mut dist = vec![vec![usize::MAX; col]; row];
    dist[start.0][start.1] = 0;
    let mut pq: BinaryHeap<Reverse<(usize, (usize, usize))>> = BinaryHeap::new();
    pq.push(Reverse((0, start)));

    let try_move_to = |to: (usize, usize), d: usize, dist: &mut Vec<Vec<usize>>, pq: &mut BinaryHeap<Reverse<(usize, (usize, usize))>>| {
        if dist[to.0][to.1] > d {
            dist[to.0][to.1] = d;
            pq.push(Reverse((d, to)));
        }
    };

    while let Some(Reverse((d, (x, y)))) = pq.pop() {
        for (i, j) in (x.saturating_sub(1)..=(x + 1).min(row - 1)).filter(|i| *i != x).map(|i| (i, y)).chain(
            (y.saturating_sub(1)..=(y + 1).min(col - 1)).filter(|j| *j != y).map(|j| (x, j))
        ) {
            match map[i][j] {
                '0' | '2' => {
                    let to = gate[i][j];
                    try_move_to(to, d + 1, &mut dist, &mut pq);
                },
                '1' | 's' => (),
                'e' => {
                    println!("{}", d + 1);
                    return;
                },
                _ => unreachable!(),
            }
        }
    }
    
    println!("-1");
}