#pragma GCC target("avx2") //#pragma GCC target("avx") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") // #include #include #include #include // #include #include #include #include #include #include // #include // #include #include // #include // #include // #include // #include #include #include using namespace boost::adaptors; // #include #include // #include // #include #include #include #include // #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include #include // #include // #include // #include // #include // #include // #include // #include #include // #include // #include // #include // #include // #include // #include // #include // #include using namespace std; #include using namespace atcoder; #define STRINGIFY(n) #n #define TOSTRING(n) STRINGIFY(n) using ll = long long; using ull = unsigned long long; template using maxque = priority_queue; template using minque = priority_queue,greater>; #define int ll #define endl "\n" #define unless(cond) if(!(cond)) #define until(cond) while(!(cond)) #define rep(i,s,e) for(ll i = (s); i < (e); ++i) #define repR(i,s,e) for(ll i = (e)-1; (s) <= i; --i) #define repE(i,s,e) for(ll i = (s); i <= (e); ++i) #define repER(i,s,e) for(ll i = (e); (s) <= i; --i) #define repSubsetR(set,super) for(ll _super=super,set = _super; 0 <= set; --set)if(set &= _super, true) #define ALL(xs) begin(xs), end(xs) #define ALLR(xs) rbegin(xs), rend(xs) #define ALLC(xs) cbegin(xs), cend(xs) #define ALLCR(xs) crbegin(xs), crend(xs) template void uniq(C &xs){ xs.erase(unique(ALL(xs)), xs.end()); } template constexpr ll len(C &&xs){ return size(forward(xs)); } ll BIT(ll n){ return 1LL< "; } template void debug_(const X &x, const Xs&... xs){ cerr << x; (void)initializer_list{ (cerr << ", " << xs,0)... };cerr << endl; }void debug_(){ cerr << endl; } #define ASSERT(pred,...) (static_cast(pred) ? void(0) : (debug_h(__FILE__, __LINE__, "ASSERT FAIL! " #pred "; " #__VA_ARGS__),debug_(__VA_ARGS__),exit(1))) template X &&dbg_(X &&x){ cerr<(x); } #ifdef DEBUG #define dbg(x) (debug_h(__FILE__, __LINE__, "" #x),dbg_(x)) #define debug(...) (debug_h(__FILE__, __LINE__, "" #__VA_ARGS__),debug_(__VA_ARGS__)) #define clk(...) (cerr << __VA_ARGS__ " @ " << (clock()-clock0) < decltype(*this); using SELF_ = decltype(((self_fn_*)nullptr)()); DEF_ORD(==) DEF_ORD(!=) DEF_ORD(<) DEF_ORD(>) DEF_ORD(<=) DEF_ORD(>=) template auto operator<<(ostream &out, const C &xs) -> enable_if_t, char*> && !is_same_v, string>, decltype(begin(xs),out)&> { out<<"[ "; for(auto&&x:xs)out< auto operator>>(istream &in, C &xs) -> enable_if_t, char*> && !is_same_v, string>, decltype(begin(xs),in)&> { for(auto&x:xs)in>>x; return in; } template void print_tuple_(ostream &out, Tuple const &xs, std::index_sequence){ out << "("; (void)initializer_list{ (out << (I==0?"":", ") << std::get(xs),0)... }; out << ")"; } template ostream &operator<<(ostream &out, tuple const &xs){ print_tuple_(out, xs, make_index_sequence()); return out; } template void read_tuple_(istream &in, Tuple &xs, std::index_sequence){ (void)initializer_list{ (in >> std::get(xs),0)... }; } template istream &operator>>(istream &in, tuple &xs){ read_tuple_(in, xs, make_index_sequence()); return in; } template ostream &operator<<(ostream &out, pair const &p){ return out << "(" << p.first << ", " << p.second << ")"; } template istream &operator>>(istream &in, pair &p){ return in >> p.first >> p.second; } template> ostream &operator<<(ostream &out, MINT x){ return out << x.val(); } template> istream &operator>>(istream &in, MINT &x){ ll a; in>>a; x = a; return in; } template void _cin(X &... x){ (cin >> ... >> x); } #define CIN(...) __VA_ARGS__; _cin(__VA_ARGS__) template struct Fix : F { template Fix(G &&g) : F{forward(g)} {} template decltype(auto) operator()(Xs&&... xs)const{ return F::operator()(*this, forward(xs)...); } }; template Fix(F&&) -> Fix>; template bool chmin(T &a, U b){ if(a <= b)return false; a = b; return true; } template bool chmax(T &a, U b){ if(a >= b)return false; a = b; return true; } //const signed MOD = 998244353; const signed MOD = 1000000007; // 10^9+7 using mint = static_modint; // using mint = dynamic_modint<-1>; // mint::set_mod(mod); // using mint0 = dynamic_modint<0>; // mint0::set_mod(mod); const ll INF = BIT(60); ll solve(){ ll CIN(h,w,u,d,r,l,k,p,sx,sy,tx,ty);--sx;--sy;--tx;--ty; vector brd(h);cin>>brd; vector dist(h, vector(w, INF)); minque> q; q.emplace(dist[sy][sx] = 0, sy, sx); while(!q.empty()){ auto [dis, y, x] = q.top(); q.pop(); vector> yxcs{ {y-1,x,u}, {y+1,x,d}, {y,x-1,l}, {y,x+1,r}, }; for(auto [y,x,cost] : yxcs){ unless(0 <= y && y < h) continue; unless(0 <= x && x < w) continue; switch(brd[y][x]){ case '#': continue; case '@': cost += p; break; case '.': break; default: exit(1); } ll dd = dis+cost; if(dd <= k && chmin(dist[y][x], dd)){ if(y==ty&&x==tx){ debug(dd); return true; } q.emplace(dd, y, x); } } } return false; } signed main(){ cin.tie(nullptr);ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); try{ cout << (solve()?"Yes":"No") << endl; // */ return 0; }catch(exception& e){ cerr << e.what() << endl; }catch(char *s){ cerr << s << endl; } return 1; }