#include #ifdef DEBUG #include #else #define dump(...) ((void)0) #endif template bool chmin(T &a, const U &b) { return (a > b ? a = b, true : false); } template bool chmax(T &a, const U &b) { return (a < b ? a = b, true : false); } template void fill_array(T (&a)[N], const U &v) { std::fill((U *) a, (U *) (a + N), v); } template auto make_vector(const std::array &a, T value = T()) { static_assert(I >= 1); static_assert(N >= 1); if constexpr (I == 1) { return std::vector(a[N - I], value); } else { return std::vector(a[N - I], make_vector(a, value)); } } template std::ostream &operator<<(std::ostream &s, const std::vector &a) { for (auto it = a.begin(); it != a.end(); ++it) { if (it != a.begin()) s << " "; s << *it; } return s; } template std::istream &operator>>(std::istream &s, std::vector &a) { for (auto &x : a) s >> x; return s; } std::string YesNo(bool value) { return value ? "Yes" : "No"; } std::string YESNO(bool value) { return value ? "YES" : "NO"; } std::string yesno(bool value) { return value ? "yes" : "no"; } template void putl(const T &value) { std::cout << value << "\n"; } template void putl(const Head head, const Tail &... tail) { std::cout << head << " "; putl(tail...); } namespace haar_lib { template struct edge { int from, to; T cost; int index = -1; edge() {} edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} edge(int from, int to, T cost, int index) : from(from), to(to), cost(cost), index(index) {} }; template struct graph { using weight_type = T; using edge_type = edge; std::vector>> data; auto& operator[](size_t i) { return data[i]; } const auto& operator[](size_t i) const { return data[i]; } auto begin() const { return data.begin(); } auto end() const { return data.end(); } graph() {} graph(int N) : data(N) {} bool empty() const { return data.empty(); } int size() const { return data.size(); } void add_edge(int i, int j, T w, int index = -1) { data[i].emplace_back(i, j, w, index); } void add_undirected(int i, int j, T w, int index = -1) { add_edge(i, j, w, index); add_edge(j, i, w, index); } template void read(int M) { for (int i = 0; i < M; ++i) { int u, v; std::cin >> u >> v; u -= I; v -= I; T w = 1; if (WEIGHTED) std::cin >> w; if (DIRECTED) add_edge(u, v, w, i); else add_undirected(u, v, w, i); } } }; template using tree = graph; } // namespace haar_lib namespace haar_lib { template auto dijkstra(const graph &graph, std::vector src) { using P = std::pair; const int n = graph.size(); std::vector> dist(n); std::vector check(n, false); std::priority_queue, std::greater

> pq; for (auto s : src) { dist[s] = 0; pq.emplace(0, s); } while (not pq.empty()) { const auto [d, i] = pq.top(); pq.pop(); if (check[i]) continue; check[i] = true; for (auto &e : graph[i]) { if (not dist[e.to]) { dist[e.to] = d + e.cost; pq.emplace(*dist[e.to], e.to); } else { if (*dist[e.to] > d + e.cost) { dist[e.to] = d + e.cost; if (not check[e.to]) pq.emplace(*dist[e.to], e.to); } } } } return dist; } } // namespace haar_lib namespace haar_lib {} namespace solver { using namespace haar_lib; constexpr int m1000000007 = 1000000007; constexpr int m998244353 = 998244353; void init() { std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(12); std::cerr << std::fixed << std::setprecision(12); std::cin.exceptions(std::ios_base::failbit); } void solve() { int H, W; std::cin >> H >> W; int64_t U, D, R, L, K, P; std::cin >> U >> D >> R >> L >> K >> P; int xs, ys, xt, yt; std::cin >> xs >> ys >> xt >> yt; --xs, --ys, --xt, --yt; std::vector C(H); std::cin >> C; graph g(H * W); auto index = make_vector({H, W}); { int k = 0; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { index[i][j] = k++; } } } for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (i - 1 >= 0 and C[i - 1][j] != '#') g.add_edge(index[i][j], index[i - 1][j], U + (C[i - 1][j] == '@' ? P : 0)); if (i + 1 < H and C[i + 1][j] != '#') g.add_edge(index[i][j], index[i + 1][j], D + (C[i + 1][j] == '@' ? P : 0)); if (j - 1 >= 0 and C[i][j - 1] != '#') g.add_edge(index[i][j], index[i][j - 1], L + (C[i][j - 1] == '@' ? P : 0)); if (j + 1 < W and C[i][j + 1] != '#') g.add_edge(index[i][j], index[i][j + 1], R + (C[i][j + 1] == '@' ? P : 0)); } } auto dist = dijkstra(g, {index[xs][ys]}); // for (int i = 0; i < H; ++i) { // for (int j = 0; j < W; ++j) { // dump(dist[index[i][j]]); // } // } auto ans = dist[index[xt][yt]]; dump(ans); std::cout << (ans and *ans <= K ? "Yes" : "No") << "\n"; } } int main() { solver::init(); while (true) { try { solver::solve(); std::cout << std::flush; std::cerr << std::flush; } catch (const std::istream::failure &e) { break; } catch (...) { break; } } return 0; }