#include #define REP(i, n) for (int i = 0; (i) < (int)(n); ++(i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++(i)) #define REP_R(i, n) for (int i = (int)(n)-1; (i) >= 0; --(i)) #define REP3R(i, m, n) for (int i = (int)(n)-1; (i) >= (int)(m); --(i)) #define ALL(x) ::std::begin(x), ::std::end(x) using namespace std; template using reversed_priority_queue = priority_queue, greater >; // generated by oj-template v4.8.0 (https://github.com/online-judge-tools/template-generator) const std::string YES = "Yes"; const std::string NO = "No"; int main() { // input int h, w, up, down, left, right; int64_t k, p; cin >> h >> w >> up >> down >> right >> left >> k >> p; int sx, sy, tx, ty; cin >> sy >> sx >> ty >> tx; -- sx; -- sy; -- tx; -- ty; vector c(h); REP (y, h) { cin >> c[y]; } // solve vector> dist(h, vector(w, INT64_MAX)); reversed_priority_queue> que; dist[sy][sx] = 0; que.emplace(0, sy, sx); while (not que.empty()) { auto [dist_y_x, y, x] = que.top(); que.pop(); if (dist_y_x > dist[y][x]) { continue; } REP (i, 4) { const int dy[4] = {-1, 1, 0, 0}; const int dx[4] = {0, 0, 1, -1}; int ny = y + dy[i]; int nx = x + dx[i]; if (0 <= ny and ny < h and 0 <= nx and nx < w) { if (c[ny][nx] == '#') { continue; } const int cost[4] = {up, down, right, left}; int64_t ndist = dist[y][x] + cost[i] + (c[ny][nx] == '@' ? p : 0); if (ndist < dist[ny][nx]) { dist[ny][nx] = ndist; que.emplace(ndist, ny, nx); } } } } bool ans = dist[ty][tx] <= k; // output cout << (ans ? YES : NO) << '\n'; return 0; }