// -*- coding: utf-8-unix -*- #![allow(dead_code, unused_imports, unused_macros, unused_variables)] use std::cmp::{max, min, Ordering, Reverse}; use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; use std::fmt::Debug; use std::io::{self, Read}; use std::str::FromStr; const INF_I32: i32 = 1_i32 << 30; const INF_I64: i64 = 1_i64 << 60; const INF_I128: i128 = 1_i128 << 120; const INF_USIZE: usize = usize::MAX / 4; const INF: i64 = INF_I64; const UINF: usize = INF_USIZE; const INF128: i128 = INF_I128; const MOD1: i64 = 1_000_000_007; const MOD9: i64 = 998_244_353; const MOD: i64 = MOD9; const UMOD: usize = MOD as usize; // ============================================================================= // Input // ========================================================================= #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat(n: usize) -> Vec> { (0..n).map(|_| read_vec()).collect() } macro_rules! uin { ($($x:ident),+ $(,)?) => { let values = read_vec::(); let mut iter = values.into_iter(); $( let mut $x = iter .next() .expect("入力の要素数が不足しています"); )+ }; } macro_rules! iin { ($($x:ident),+ $(,)?) => { let values = read_vec::(); let mut iter = values.into_iter(); $( let mut $x = iter .next() .expect("入力の要素数が不足しています"); )+ }; } macro_rules! cin { ($x:ident $(,)?) => { let mut $x: Vec = read::().chars().collect(); }; } macro_rules! inuv { ($x:ident $(,)?) => { let mut $x = read_vec::(); }; } macro_rules! iniv { ($x:ident $(,)?) => { let mut $x = read_vec::(); }; } // ============================================================================= // Output / Debug // ============================================================================= macro_rules! p { () => { println!(); }; ($value:expr $(,)?) => { println!("{}", $value); }; ($fmt:literal, $($arg:tt)*) => { println!($fmt, $($arg)*); }; } macro_rules! join { ($iter:expr, $separator:expr $(,)?) => { ($iter) .into_iter() .map(|x| x.to_string()) .collect::>() .join($separator) }; } macro_rules! pv { ($iter:expr $(,)?) => { println!("{}", join!($iter, " ")); }; ($iter:expr, $separator:expr $(,)?) => { println!("{}", join!($iter, $separator)); }; } macro_rules! yesno { ($condition:expr $(,)?) => { println!("{}", if $condition { "Yes" } else { "No" }); }; ($condition:expr, $yes:expr, $no:expr $(,)?) => { println!("{}", if $condition { $yes } else { $no }); }; } macro_rules! d { ($($value:expr),+ $(,)?) => { #[cfg(debug_assertions)] { eprint!("[{}:{}]", file!(), line!()); $( eprint!(" {} = {:?}", stringify!($value), &$value); )+ eprintln!(); } }; } // ============================================================================= // Scalar / Vec utilities // ============================================================================= macro_rules! chmin { ($base:expr, $($value:expr),+ $(,)?) => {{ let mut updated = false; $( let value = $value; if $base > value { $base = value; updated = true; } )+ updated }}; } macro_rules! chmax { ($base:expr, $($value:expr),+ $(,)?) => {{ let mut updated = false; $( let value = $value; if $base < value { $base = value; updated = true; } )+ updated }}; } macro_rules! min { // collection: Vec、配列、スライスなど ($iter:expr $(,)?) => {{ ($iter) .iter() .min() .cloned() .expect("min! called on an empty iterator") }}; // 複数の値 ($first:expr, $($rest:expr),+ $(,)?) => {{ let mut answer = ($first).clone(); $( chmin!(answer, ($rest).clone()); )+ answer }}; } macro_rules! max { // collection: Vec、配列、スライスなど ($iter:expr $(,)?) => {{ ($iter) .iter() .max() .cloned() .expect("max! called on an empty iterator") }}; // 複数の値 ($first:expr, $($rest:expr),+ $(,)?) => {{ let mut answer = ($first).clone(); $( chmax!(answer, ($rest).clone()); )+ answer }}; } macro_rules! ndvec { ($value:expr; $len:expr) => { vec![$value; $len] }; ($value:expr; $len:expr, $($rest:expr),+ $(,)?) => { vec![ndvec![$value; $($rest),+]; $len] }; } macro_rules! prefix_sum { ($values:expr $(,)?) => {{ let values = &$values; let mut prefix = Vec::with_capacity(values.len() + 1); prefix.push(Default::default()); for &value in values.iter() { let next = prefix.last().copied().unwrap() + value; prefix.push(next); } prefix }}; } // 数学的な floor(a / b)。b != 0。 macro_rules! div_floor { ($a:expr, $b:expr $(,)?) => {{ let a = $a; let b = $b; let q = a / b; let r = a % b; if r != 0 && ((r > 0) != (b > 0)) { q - 1 } else { q } }}; } // 数学的な ceil(a / b)。b != 0。 macro_rules! div_ceil { ($a:expr, $b:expr $(,)?) => {{ let a = $a; let b = $b; let q = a / b; let r = a % b; if r != 0 && ((r > 0) == (b > 0)) { q + 1 } else { q } }}; } // ============================================================================= // Integer / floating-point binary search // ============================================================================= // pred(ok) == true, pred(ng) == false を保ち、最後に true 側の境界を返す。 // ok < ng と ok > ng の双方に対応する。 macro_rules! binsearch { (ok = $ok:expr, ng = $ng:expr, $pred:expr $(,)?) => {{ let mut ok = $ok; let mut ng = $ng; let mut pred = $pred; while ok.abs_diff(ng) > 1 { let mid = if ok < ng { ok + (ng - ok) / 2 } else { ng + (ok - ng) / 2 }; if pred(mid) { ok = mid; } else { ng = mid; } } ok }}; } // false ... true の単調列に対し、最初の true を返す。 // ng は false 側の番兵、ok は true 側の番兵。 macro_rules! first_true { ($ng:expr, $ok:expr, $pred:expr $(,)?) => { binsearch!(ok = $ok, ng = $ng, $pred) }; } // true ... false の単調列に対し、最後の true を返す。 // ok は true 側の番兵、ng は false 側の番兵。 macro_rules! last_true { ($ok:expr, $ng:expr, $pred:expr $(,)?) => { binsearch!(ok = $ok, ng = $ng, $pred) }; } // 浮動小数点版。回数を明示することで停止条件の曖昧さを避ける。 macro_rules! binsearch_f64 { (ok = $ok:expr, ng = $ng:expr, iter = $iter:expr, $pred:expr $(,)?) => {{ let mut ok = $ok; let mut ng = $ng; let mut pred = $pred; for _ in 0..$iter { let mid = (ok + ng) * 0.5; if pred(mid) { ok = mid; } else { ng = mid; } } ok }}; } // ============================================================================= // Sorted slice bounds // ============================================================================= macro_rules! lower_bound { ($slice:expr, $value:expr $(,)?) => {{ let value = $value; ($slice).partition_point(|x| x < &value) }}; } macro_rules! upper_bound { ($slice:expr, $value:expr $(,)?) => {{ let value = $value; ($slice).partition_point(|x| x <= &value) }}; } // UTIL macro_rules! neighbors4 { ($y:expr, $x:expr, $h:expr, $w:expr $(,)?) => {{ const DY: [isize; 4] = [-1, 0, 1, 0]; const DX: [isize; 4] = [0, 1, 0, -1]; (0..4).filter_map(move |dir| { let ny = $y as isize + DY[dir]; let nx = $x as isize + DX[dir]; if 0 <= ny && ny < $h as isize && 0 <= nx && nx < $w as isize { Some((ny as usize, nx as usize)) } else { None } }) }}; } macro_rules! run_length { ($iter:expr $(,)?) => {{ let mut result = Vec::new(); for value in $iter { match result.last_mut() { Some((last, count)) if *last == value => { *count += 1usize; } _ => { result.push((value, 1usize)); } } } result }}; } macro_rules! vector_compress { ($iter:expr $(,)?) => {{ let values: Vec<_> = ($iter).into_iter().collect(); let mut coordinates = values.clone(); coordinates.sort(); coordinates.dedup(); let compressed = values .iter() .map(|value| coordinates.binary_search(value).unwrap()) .collect::>(); (compressed, coordinates) }}; } // ============================================================================= // Map / Set literals and counters // ============================================================================= macro_rules! map { ($($key:expr => $value:expr),* $(,)?) => {{ let mut map = ::std::collections::BTreeMap::new(); $(map.insert($key, $value);)* map }}; } macro_rules! set { ($($value:expr),* $(,)?) => {{ let mut set = ::std::collections::BTreeSet::new(); $(set.insert($value);)* set }}; } macro_rules! count_map { ($iter:expr $(,)?) => {{ let mut count = BTreeMap::new(); for value in $iter { *count.entry(value).or_insert(0usize) += 1; } count }}; } macro_rules! map_add { ($map:expr, $key:expr, $delta:expr $(,)?) => {{ let key = $key; let delta = $delta; let map = &mut $map; *map.entry(key).or_insert(0) += delta; }}; } macro_rules! map_inc { ($map:expr, $key:expr $(,)?) => { map_add!($map, $key, 1) }; } macro_rules! map_sub { ($map:expr, $key:expr, $delta:expr $(,)?) => {{ let key = $key; let delta = $delta; let map = &mut $map; let remove = match map.get_mut(&key) { Some(value) => { if *value <= delta { true } else { *value -= delta; false } } None => false, }; if remove { map.remove(&key); true } else { false } }}; } macro_rules! map_dec { ($map:expr, $key:expr $(,)?) => { map_sub!($map, $key, 1) }; } macro_rules! sum { ($iter:expr $(,)?) => {{ let mut sum = 0; for &value in ($iter).iter() { sum += value; } sum }}; } fn grid_01bfs(mat: &Vec>, start: (usize, usize)) -> Vec> { let h = mat.len(); let w = mat[0].len(); let mut res = vec![vec![INF as usize; (w) as usize]; (h) as usize]; let mut q = VecDeque::new(); q.push_back(start); res[start.0][start.1] = 0; while !q.is_empty() { let v = q.pop_front().unwrap(); for i in -1..=1 { for j in -1..=1 { if (i * j as i32).abs() == 1 || (i == 0 && j == 0) { continue; } if v.0 == 0 && i == -1 { continue; } if v.0 == h - 1 && i == 1 { continue; } if v.1 == 0 && j == -1 { continue; } if v.1 == w - 1 && j == 1 { continue; } let nv = ((v.0 as i32 + i) as usize, (v.1 as i32 + j) as usize); let mut d = 1; if mat[nv.0][nv.1] == 1 { d = 1; } else { d = 0; } if (res[nv.0][nv.1] > res[v.0][v.1] + d) { res[nv.0][nv.1] = res[v.0][v.1] + d; if d == 0 { q.push_front(nv); } else { q.push_back(nv); } } } } } return res; } fn grid_bfs(mat: &Vec>, start: (usize, usize)) -> Vec> { let h = mat.len(); let w = mat[0].len(); let mut res = vec![vec![INF as usize; (w) as usize]; (h) as usize]; let mut q = VecDeque::new(); q.push_back(start); res[start.0][start.1] = 0; while !q.is_empty() { let v = q.pop_front().unwrap(); for i in -1..=1 { for j in -1..=1 { if (i * j as i32).abs() == 1 || (i == 0 && j == 0) { continue; } if v.0 == 0 && i == -1 { continue; } if v.0 == h - 1 && i == 1 { continue; } if v.1 == 0 && j == -1 { continue; } if v.1 == w - 1 && j == 1 { continue; } let nv = ((v.0 as i32 + i) as usize, (v.1 as i32 + j) as usize); let mut d = 1; if mat[nv.0][nv.1] == 1 { continue; } else { d = 1; } if res[nv.0][nv.1] > res[v.0][v.1] + d { res[nv.0][nv.1] = res[v.0][v.1] + d; if d == 0 { q.push_front(nv); } else { q.push_back(nv); } } } } } return res; } fn main() { uin!(h, w); let mut grid = vec![vec![0; w]; h]; uin!(a, b); uin!(r1, c1, r2, c2); uin!(p, q); let mut d1 = grid_bfs(&grid, (a - 1, b - 1)); let mut d2 = grid_bfs(&grid, (p - 1, q - 1)); let mut res = UINF; for i in r1 - 1..r2 { for j in c1 - 1..c2 { res = min(res, d1[i][j] + d2[i][j] + d1[p - 1][q - 1]); } } p!(res); }