#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::(); let (h, w) = (v[0], v[1]); let v = read_vec::(); let (u, d, r, l, k, p) = (v[0], v[1], v[2], v[3], v[4], v[5]); let v = read_vec::(); let (xs, ys, xt, yt) = (v[0] - 1, v[1] - 1, v[2] - 1, v[3] - 1); let mut grid = vec![vec![]; h]; for i in 0..h { grid[i] = read::().chars().collect::>(); } let to_index = |x, y| x + y * w; let mut edges = vec![vec![]; w * h]; for y in 0..h { for x in 0..w { if grid[y][x] == '#' { continue; } let cost = if grid[y][x] == '@' { p } else { 0 }; let cur = to_index(x, y); if x > 0 { let adj = to_index(x - 1, y); edges[cur].push((adj, l + cost)); } if y > 0 { let adj = to_index(x, y - 1); edges[cur].push((adj, u + cost)); } if x < w - 1 { let adj = to_index(x + 1, y); edges[cur].push((adj, r + cost)); } if y < h - 1 { let adj = to_index(x, y + 1); edges[cur].push((adj, d + cost)); } } } let s = to_index(ys, xs); let t = to_index(yt, xt); let d = solve(&edges, s); debug!(s, t, d); if d[t] <= k { println!("Yes"); } else { println!("No"); } } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } type Cost = i64; const INF: Cost = 100000_00000_00000; fn solve(edges: &Vec>, start_idx: usize) -> Vec { let num_apexes = edges.len(); let mut d = vec![INF; num_apexes]; d[start_idx] = 0; let mut que = std::collections::BinaryHeap::new(); que.push((std::cmp::Reverse(0), start_idx)); while let Some((u, v)) = que.pop() { if d[v] < u.0 { continue; } for e in &edges[v] { if d[v] != INF && d[e.0] > d[v] + e.1 { d[e.0] = d[v] + e.1; que.push((std::cmp::Reverse(d[e.0]), e.0)); } } } d }