use std::collections::{HashMap, HashSet}; fn main() { proconio::input! { h: i64, w:i64, s: (i64, i64), g: (i64, i64), b: [String; h], } let s = (s.1 - 1, s.0 - 1); let g = (g.1 - 1, g.0 - 1); let b = b .into_iter() .map(|s| { s.chars() .map(|x| x.to_digit(10).unwrap() as i8) .collect::>() }) .collect::>(); let mut movable: HashMap<(i64, i64), Vec<(i64, i64)>> = HashMap::new(); // 横 for y in 0..h { for x in 0..w - 1 { if (b[y as usize][x as usize] - b[y as usize][x as usize + 1]).abs() <= 1 { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x + 1, y)); } else { movable.insert((x, y), vec![(x + 1, y)]); } if let Some(v) = movable.get_mut(&(x + 1, y)) { v.push((x, y)); } else { movable.insert((x + 1, y), vec![(x, y)]); } } } } for y in 0..h { for x in 0..w - 2 { if b[y as usize][x as usize] == b[y as usize][x as usize + 2] && b[y as usize][x as usize] > b[y as usize][x as usize + 1] { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x + 2, y)); } else { movable.insert((x, y), vec![(x + 2, y)]); } if let Some(v) = movable.get_mut(&(x + 2, y)) { v.push((x, y)); } else { movable.insert((x + 2, y), vec![(x, y)]); } } } } // 縦 for y in 0..h - 1 { for x in 0..w { if (b[y as usize][x as usize] - b[y as usize + 1][x as usize]).abs() <= 1 { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x, y + 1)); } else { movable.insert((x, y), vec![(x, y + 1)]); } if let Some(v) = movable.get_mut(&(x, y + 1)) { v.push((x, y)); } else { movable.insert((x, y + 1), vec![(x, y)]); } } } } for y in 0..h - 2 { for x in 0..w { if b[y as usize][x as usize] == b[y as usize + 2][x as usize] && b[y as usize][x as usize] > b[y as usize + 1][x as usize] { if let Some(v) = movable.get_mut(&(x, y)) { v.push((x, y + 2)); } else { movable.insert((x, y), vec![(x, y + 2)]); } if let Some(v) = movable.get_mut(&(x, y + 2)) { v.push((x, y)); } else { movable.insert((x, y + 2), vec![(x, y)]); } } } } let mut from = HashSet::new(); let mut visited = HashSet::new(); from.insert(s); let goal = loop { let mut to = HashSet::new(); for from in from { if let Some(v) = movable.get(&from) { for t in v { if !visited.contains(t) { visited.insert(*t); to.insert(*t); } } } } // ゴールに到着したらtrue if to.contains(&g) { break true; } // 行ける場所がなくなったらfalse if to.is_empty() { break false; } from = to; }; if goal { println!("YES"); } else { println!("NO"); } }