提出 #16152316

---

ソースコード 拡げる

#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  dead_code,
  unused_macros
)]
//use proconio::fastout;
use proconio::input;
use proconio::marker::*;
//use std::collections::HashSet;
use std::cmp::*;
use std::collections::*;
macro_rules! debug {
  ($($a:expr),* $(,)*) => {
      #[cfg(debug_assertions)]
      eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
  };
}
fn main() {
  input! {
     H:usize,
     W:usize,
     C:(Usize1, Usize1),
     D:(Usize1, Usize1),
     S:[Chars;H]
  }
  let C: (usize, usize) = (C.0 + 2, C.1 + 2);
  let D: (usize, usize) = (D.0 + 2, D.1 + 2);
  let S: Vec<Vec<char>> = S;
  let mut kabe = vec![vec![true; W + 10]; H + 10];
  for x in 0..H {
    for y in 0..W {
      if S[x][y] == '.' {
        kabe[x + 2][y + 2] = false;
      }
    }
  }
  let kabe: Vec<Vec<bool>> = kabe;
  // Cを基準に幅優先探索。
  // (n=ワープ回数, 位置)
  let mut h = BinaryHeap::new();
  //訪問済み
  let mut v = vec![vec![false; W + 10]; H + 10];
  // ワープ回数
  let mut d = vec![vec![std::u64::MAX; W + 10]; H + 10];
  v[C.0][C.1] = true;
  d[C.0][C.1] = 0;
  h.push((Reverse(0), C.0, C.1));
  while let Some((Reverse(c), x, y)) = h.pop() {
    toho(&kabe, &mut d, &mut h, c, x - 1, y);
    toho(&kabe, &mut d, &mut h, c, x + 1, y);
    toho(&kabe, &mut d, &mut h, c, x, y - 1);
    toho(&kabe, &mut d, &mut h, c, x, y + 1);

    warp(&kabe, &mut d, &mut h, c, x - 2, y - 2);
    warp(&kabe, &mut d, &mut h, c, x - 2, y - 1);
    warp(&kabe, &mut d, &mut h, c, x - 2, y);
    warp(&kabe, &mut d, &mut h, c, x - 2, y + 1);
    warp(&kabe, &mut d, &mut h, c, x - 2, y + 2);
    warp(&kabe, &mut d, &mut h, c, x - 1, y - 2);
    warp(&kabe, &mut d, &mut h, c, x - 1, y - 1);
    warp(&kabe, &mut d, &mut h, c, x - 1, y + 1);
    warp(&kabe, &mut d, &mut h, c, x - 1, y + 2);
    warp(&kabe, &mut d, &mut h, c, x, y - 2);
    warp(&kabe, &mut d, &mut h, c, x, y + 2);
    warp(&kabe, &mut d, &mut h, c, x + 1, y - 2);
    warp(&kabe, &mut d, &mut h, c, x + 1, y - 1);
    warp(&kabe, &mut d, &mut h, c, x + 1, y + 1);
    warp(&kabe, &mut d, &mut h, c, x + 1, y + 2);
    warp(&kabe, &mut d, &mut h, c, x + 2, y - 2);
    warp(&kabe, &mut d, &mut h, c, x + 2, y - 1);
    warp(&kabe, &mut d, &mut h, c, x + 2, y);
    warp(&kabe, &mut d, &mut h, c, x + 2, y + 1);
    warp(&kabe, &mut d, &mut h, c, x + 2, y + 2);
  }
  let ans = d[D.0][D.1];
  if ans < std::u64::MAX {
    println!("{}", ans);
  } else {
    println!("-1");
  }
}

fn warp(
  kabe: &Vec<Vec<bool>>,
  d: &mut Vec<Vec<u64>>,
  h: &mut BinaryHeap<(Reverse<u64>, usize, usize)>,
  c: u64,
  x: usize,
  y: usize,
) -> () {
  if kabe[x][y] == false {
    let c = c + 1;
    if d[x][y] > c {
      d[x][y] = c;
      h.push((Reverse(c), x, y));
    }
  }
}

fn toho(
  kabe: &Vec<Vec<bool>>,
  d: &mut Vec<Vec<u64>>,
  h: &mut BinaryHeap<(Reverse<u64>, usize, usize)>,
  c: u64,
  x: usize,
  y: usize,
) -> bool {
  if kabe[x][y] == false {
    if d[x][y] > c {
      d[x][y] = c;
      h.push((Reverse(c), x, y));
    }
    true
  } else {
    false
  }
}

提出情報

ジャッジ結果