use proconio::{input, marker::Usize1}; fn main() { input! { h: usize, w: usize, a: Usize1, b: Usize1, r1: Usize1, c1: Usize1, r2: Usize1, c2: Usize1, p: Usize1, q: Usize1, } let from_iwai_dist = grid_bfs(h, w, (a, b)); let from_trash_dist = grid_bfs(h, w, (p, q)); let mut ans = 1 << 60; for r in r1..=r2 { for c in c1..=c2 { ans = ans.min(from_iwai_dist[r][c] + from_trash_dist[r][c]); } } println!("{}", ans + from_trash_dist[a][b]); } pub fn grid_bfs(h: usize, w: usize, s: (usize, usize)) -> Vec> { let inf: usize = 1 << 30; let dx: [i32; 4] = [1, 0, -1, 0]; let dy: [i32; 4] = [0, 1, 0, -1]; let mut dist = vec![vec![inf; w]; h]; let mut que = std::collections::VecDeque::new(); dist[s.0][s.1] = 0; que.push_back(s); while let Some((x, y)) = que.pop_front() { for dir in 0..4 { let nx = x as i32 + dx[dir]; let ny = y as i32 + dy[dir]; if nx < 0 || h as i32 <= nx || ny < 0 || w as i32 <= ny { continue; } let nx = nx as usize; let ny = ny as usize; if dist[nx][ny] != inf { continue; } dist[nx][ny] = dist[x][y] + 1; que.push_back((nx, ny)) } } dist }