【Rust】迷路のゴールを幅優先探索で探す

壁は9, 既に行ったところは2、行ったことない場所は0、ゴールは1　とする問題設定が素晴らしいね。上下左右のマスをこれから行く場所として追加していくロジックも面白い。

use std::collections::VecDeque;

fn main() {
    let mut maze = [
        [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
        [9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9],
        [9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 9, 9],
        [9, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9],
        [9, 0, 0, 0, 9, 0, 0, 9, 9, 0, 9, 9],
        [9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 9],
        [9, 0, 0, 0, 9, 0, 9, 0, 0, 9, 1, 9],
        [9, 0, 9, 0, 0, 0, 0, 9, 0, 0, 9, 9],
        [9, 0, 0, 9, 0, 9, 0, 0, 9, 0, 0, 9],
        [9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9],
        [9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9],
        [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
    ];

    let mut pos: VecDeque<[usize; 3]> = vec![[1, 1, 0]].into();

    while pos.len() > 0 {
        let p = pos.pop_front().unwrap(); // x, y, depth

        if maze[p[0]][p[1]] == 1 {
            println!("ゴール:{}-{}", p[0], p[1]); 
            println!("移動回数:{}", p[2]); // z
            break;
        }
        maze[p[0]][p[1]] = 2;

        if maze[p[0] - 1][p[1]] < 2 {
            pos.push_back([p[0]- 1, p[1], p[2] + 1]);
        }
        if maze[p[0] + 1][p[1]] < 2 {
            pos.push_back([p[0]+1, p[1], p[2] + 1]);
        }
        if maze[p[0]][p[1] - 1] < 2 {
            pos.push_back([p[0], p[1] -1, p[2] + 1]);
        }
        if maze[p[0]][p[1] + 1] < 2 {
            pos.push_back([p[0], p[1] + 1, p[2] + 1]);
        }
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.26s
Running `target/debug/rust`
ゴール:6-10
移動回数:28