// 前に進んだらE=0となる // 戻って進む時だけEが非ゼロになる // (x, y) から // (k, y-1), (k, y + 1) (k <= x + 1) にはコスト0で行ける // 2回移動するパターン // 戻って通常ジャンプorブーストジャンプ // // ブーストジャンプするなら後退する場所はxが最小のところでいい // S の条件から楽できる // 通常ジャンプのパターンがようわからん // いや、これはxが最大の場所に飛べばいい // それで網羅できる // // 以上のことをそのまま実装すると3乗になる // setで丁寧にやるといい? use std::collections::*; type Set = BTreeSet; fn run() { input! { h: usize, w: usize, src: (usize1, usize1), dst: (usize1, usize1), s: [bytes; h], } let mut up = vec![vec![h; w]; h]; for i in 0..h { for j in 0..w { if s[i][j] == b'.' { up[i][j] = i; } else { up[i][j] = up[i - 1][j]; } } } let mut set = vec![Set::new(); w]; for (i, s) in s.iter().enumerate() { for (set, s) in set.iter_mut().zip(s.iter()) { if *s == b'.' { set.insert(i); } } } let inf = 2000 * 2000; let mut dp = vec![vec![inf; w]; h]; dp[src.0][src.1] = 0; set[src.1].remove(&src.0); let mut now = vec![src]; while !now.is_empty() { let d = dp[now[0].0][now[0].1]; for i in 0.. { if i >= now.len() { break; } let (x, y) = now[i]; for &y in [y - 1, y + 1].iter().filter(|y| **y < w) { { let set = &mut set[y]; let pos = set.range(..=(x + 1)).cloned().collect::>(); for x in pos { set.remove(&x); dp[x][y] = d; now.push((x, y)); } } if x + 1 < h { let z = up[x + 1][y]; let e = x.saturating_sub(z); for &y in [y - 1, y + 1].iter().filter(|y| **y < w) { let set = &mut set[y]; let pos = set.range(..=(z + 1 + e / 2)).cloned().collect::>(); for x in pos { set.remove(&x); dp[x][y] = d; now.push((x, y)); } } } } } let mut next = vec![]; for (x, y) in now { for &y in [y - 2, y, y + 2].iter().filter(|y| **y < w) { let set = &mut set[y]; let pos = set.range(..=(x + 1)).cloned().collect::>(); for x in pos { set.remove(&x); dp[x][y] = d + 1; next.push((x, y)); } } } now = next; } let mut ans = dp[dst.0][dst.1]; if ans == inf { ans = -1; } println!("{}", ans); } fn main() { run(); } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ----------