#include using namespace std; #define overload3(_1, _2, _3, name, ...) name #define rep1(n) for (decltype(n) _tmp = 0; _tmp < (n); _tmp++) #define rep2(i, n) for (decltype(n) i = 0; i < (n); i++) #define rep3(i, a, b) for (decltype(b) i = a; i < (b); i++) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #if __has_include() #include #else #define dbg(...) (void(0)) #endif struct IOSetup { IOSetup() noexcept { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template void drop(const T &x) { cout << x << "\n"; exit(0); } template bool chmax(T &a, const T &b) { return a < b and (a = b, true); } template bool chmin(T &a, const T &b) { return a > b and (a = b, true); } using i64 = long long; using f64 = long double; /** * @brief Dijkstra's Algorithm * @note Find SSSP;Single Source Shortest Path in $O(|E|log|V|)$. There must be no negative edges. Return -1 for unreachable vertex. */ template vector dijkstra(vector>> const &graph, size_t root) { static_assert(is_signed::value, "template parameter T must be signed type!"); using P = pair; constexpr T INF = numeric_limits::max() / 2; vector dist(size(graph), INF); priority_queue, greater<>> pq; pq.emplace(dist[root] = 0, root); while (not empty(pq)) { const auto [c, from] = pq.top(); pq.pop(); if (dist[from] < c) continue; for (const auto &[to, cost]: graph[from]) if (chmin(dist[to], dist[from] + cost)) pq.emplace(dist[to], to); } for (auto &&e: dist) if (e == INF) e = -1; return dist; } int main() { size_t h, w, sx, sy, gx, gy; i64 u, d, r, l, k, p; cin >> h >> w >> u >> d >> r >> l >> k >> p >> sx >> sy >> gx >> gy; vector grid(h); for (auto &&i: grid) cin >> i; vector graph(h * w, vector>{}); auto ind = [&w](size_t i, size_t j) { return w * i + j; }; rep(i, h) rep(j, w) { if (i > 0 and grid[i - 1][j] != '#') graph[ind(i, j)].emplace_back(pair{ind(i - 1, j), u + p * (grid[i - 1][j] == '@')}); if (j > 0 and grid[i][j - 1] != '#') graph[ind(i, j)].emplace_back(pair{ind(i, j - 1), l + p * (grid[i][j - 1] == '@')}); if (i + 1 < h and grid[i + 1][j] != '#') graph[ind(i, j)].emplace_back(pair{ind(i + 1, j), d + p * (grid[i + 1][j] == '@')}); if (j + 1 < w and grid[i][j + 1] != '#') graph[ind(i, j)].emplace_back(pair{ind(i, j + 1), r + p * (grid[i][j + 1] == '@')}); } auto dist = dijkstra(graph, ind(sx - 1, sy - 1)); auto ans = dist[ind(gx - 1, gy - 1)] <= k and dist[ind(gx - 1, gy - 1)] != -1; cout << (ans ? "Yes\n" : "No\n"); dbg(graph); dbg(dist); }