use std::collections::BinaryHeap;
type Cell = (usize, usize);
#[inline]
fn neighbors((x,y): Cell, h: usize, w: usize) -> Vec<Cell> {
let mut res = vec![];
if x + 1 < h {
res.push((x+1,y));
}
if y + 1 < w {
res.push((x, y+1));
}
if x > 0 {
res.push((x-1,y));
}
if y > 0 {
res.push((x, y-1));
}
res
}
type State = (usize, Cell);
fn main() {
let maze = vec![
".#....",
"...##.",
"#.#...",
"..#.#.",
".#...#",
"...#.."
];
let start = (0,0);
let h = maze.len();
let w = maze[0].len();
let goal = (h-1, w-1);
let mut queue = BinaryHeap::<State>::new();
queue.push((0, start));
let inf = 100;
let mut steps = vec![vec![inf; w]; h];
loop {
match queue.pop() {
None => break,
Some((step, c)) => {
// これが気になる
if maze[c.0].chars().nth(c.1) == Some('#') || steps[c.0][c.1] < inf {
continue;
}
steps[c.0][c.1] = step;
for nc in neighbors(c, h, w) {
queue.push((step + 1, nc));
}
}
}
}
println!("{}", steps[goal.0][goal.1]);
}
dXNlIHN0ZDo6Y29sbGVjdGlvbnM6OkJpbmFyeUhlYXA7Cgp0eXBlIENlbGwgPSAodXNpemUsIHVzaXplKTsKCiNbaW5saW5lXQpmbiBuZWlnaGJvcnMoKHgseSk6IENlbGwsIGg6IHVzaXplLCB3OiB1c2l6ZSkgLT4gVmVjPENlbGw+IHsKICAgIGxldCBtdXQgcmVzID0gdmVjIVtdOwogICAgaWYgeCArIDEgPCBoIHsKICAgICAgICByZXMucHVzaCgoeCsxLHkpKTsKICAgIH0KICAgIGlmIHkgKyAxIDwgdyB7CiAgICAgICAgcmVzLnB1c2goKHgsIHkrMSkpOwogICAgfQogICAgaWYgeCA+IDAgewogICAgICAgIHJlcy5wdXNoKCh4LTEseSkpOwogICAgfQogICAgaWYgeSA+IDAgewogICAgICAgIHJlcy5wdXNoKCh4LCB5LTEpKTsKICAgIH0KICAgIHJlcwp9Cgp0eXBlIFN0YXRlID0gKHVzaXplLCBDZWxsKTsKCmZuIG1haW4oKSB7CiAgICBsZXQgbWF6ZSA9IHZlYyFbCiAgICAgICAgIi4jLi4uLiIsCiAgICAgICAgIi4uLiMjLiIsCiAgICAgICAgIiMuIy4uLiIsCiAgICAgICAgIi4uIy4jLiIsCiAgICAgICAgIi4jLi4uIyIsCiAgICAgICAgIi4uLiMuLiIKICAgIF07CiAgICBsZXQgc3RhcnQgPSAoMCwwKTsKICAgIGxldCBoID0gbWF6ZS5sZW4oKTsKICAgIGxldCB3ID0gbWF6ZVswXS5sZW4oKTsKICAgIGxldCBnb2FsID0gKGgtMSwgdy0xKTsKICAgIAogICAgbGV0IG11dCBxdWV1ZSA9IEJpbmFyeUhlYXA6OjxTdGF0ZT46Om5ldygpOwogICAgcXVldWUucHVzaCgoMCwgc3RhcnQpKTsKICAgIGxldCBpbmYgPSAxMDA7CiAgICBsZXQgbXV0IHN0ZXBzID0gdmVjIVt2ZWMhW2luZjsgd107IGhdOwogICAgbG9vcCB7CiAgICAgICAgbWF0Y2ggcXVldWUucG9wKCkgewogICAgICAgICAgICBOb25lID0+IGJyZWFrLAogICAgICAgICAgICBTb21lKChzdGVwLCBjKSkgPT4gewogICAgICAgICAgICAgICAgLy8g44GT44KM44GM5rCX44Gr44Gq44KLCiAgICAgICAgICAgICAgICBpZiBtYXplW2MuMF0uY2hhcnMoKS5udGgoYy4xKSA9PSBTb21lKCcjJykgfHwgc3RlcHNbYy4wXVtjLjFdIDwgaW5mIHsKICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHN0ZXBzW2MuMF1bYy4xXSA9IHN0ZXA7CiAgICAgICAgICAgICAgICBmb3IgbmMgaW4gbmVpZ2hib3JzKGMsIGgsIHcpIHsKICAgICAgICAgICAgICAgICAgICBxdWV1ZS5wdXNoKChzdGVwICsgMSwgbmMpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHByaW50bG4hKCJ7fSIsIHN0ZXBzW2dvYWwuMF1bZ29hbC4xXSk7Cn0=