fork download
copy 
  1. use std::collections::BinaryHeap;
  2.  
  3. type Cell = (usize, usize);
  4.  
  5. #[inline]
  6. fn neighbors((x,y): Cell, h: usize, w: usize) -> Vec<Cell> {
  7.     let mut res = vec![];
  8.     if x + 1 < h {
  9.         res.push((x+1,y));
  10.     }
  11.     if y + 1 < w {
  12.         res.push((x, y+1));
  13.     }
  14.     if x > 0 {
  15.         res.push((x-1,y));
  16.     }
  17.     if y > 0 {
  18.         res.push((x, y-1));
  19.     }
  20.     res
  21. }
  22.  
  23. type State = (usize, Cell);
  24.  
  25. fn main() {
  26.     let maze = vec![
  27.         ".#....",
  28.         "...##.",
  29.         "#.#...",
  30.         "..#.#.",
  31.         ".#...#",
  32.         "...#.."
  33.     ];
  34.     let start = (0,0);
  35.     let h = maze.len();
  36.     let w = maze[0].len();
  37.     let goal = (h-1, w-1);
  38.  
  39.     let mut queue = BinaryHeap::<State>::new();
  40.     queue.push((0, start));
  41.     let inf = 100;
  42.     let mut steps = vec![vec![inf; w]; h];
  43.     loop {
  44.         match queue.pop() {
  45.             None => break,
  46.             Some((step, c)) => {
  47.                 // これが気になる
  48.                 if maze[c.0].chars().nth(c.1) == Some('#') || steps[c.0][c.1] < inf {
  49.                     continue;
  50.                 }
  51.                 steps[c.0][c.1] = step;
  52.                 for nc in neighbors(c, h, w) {
  53.                     queue.push((step + 1, nc));
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     println!("{}", steps[goal.0][goal.1]);
  59. }
Success #stdin #stdout 0s 14912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14
https://ideone.com/3yRoBI
language:
Rust (rust 1.56)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!