/* -*- coding: utf-8 -*- * * 1638.cc: No.1638 Robot Maze - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_H = 100; const int MAX_W = 100; const int MAX_N = MAX_H * MAX_W; const long long LINF = 1LL << 62; const int dys[] = { -1, 1, 0, 0 }, dxs[] = { 0, 0, 1, -1 }; enum { DU, DD, DR, DL }; /* typedef */ typedef long long ll; typedef pair pli; /* global variables */ char fs[MAX_H][MAX_W + 4]; ll ds[MAX_N]; /* subroutines */ inline int yx2p(int y, int x, int w) { return y * w + x; } inline void p2yx(int p, int &y, int &x, int w) { y = p / w, x = p % w; } /* main */ int main() { int h, w, dcs[4], p, sy, sx, gy, gx; ll k; scanf("%d%d%d%d%d%d%lld%d%d%d%d%d", &h, &w, dcs + DU, dcs + DD, dcs + DR, dcs + DL, &k, &p, &sy, &sx, &gy, &gx); sy--, sx--, gy--, gx--; int st = yx2p(sy, sx, w), gl = yx2p(gy, gx, w); for (int y = 0; y < h; y++) scanf("%s", fs[y]); fill(ds, ds + h * w, LINF); ds[st] = 0; priority_queue q; q.push(pli(0, st)); while (! q.empty()) { pli u = q.top(); q.pop(); ll ud = -u.first; int up = u.second; if (up == gl) break; int uy, ux; p2yx(up, uy, ux, w); for (int di = 0; di < 4; di++) { int vy = uy + dys[di], vx = ux + dxs[di]; if (vy >= 0 && vy < h && vx >= 0 && vx < w && fs[vy][vx] != '#') { int vp = yx2p(vy, vx, w); ll vd = ud + dcs[di] + (fs[vy][vx] == '@' ? p : 0); if (ds[vp] > vd) { ds[vp] = vd; q.push(pli(-vd, vp)); } } } } if (ds[gl] <= k) puts("Yes"); else puts("No"); return 0; }