This documentation is automatically generated by online-judge-tools/verification-helper
// verification-helper: PROBLEM https://yukicoder.me/problems/6680
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../io/single.cpp"
#include "../../graph/grid.cpp"
#include "../../graph/dijkstra.cpp"
#undef call_from_test
signed main(){
using ll = long long;
cin.tie(0);
ios::sync_with_stdio(0);
int h,w;
cin>>h>>w;
ll u,d,r,l,k,p;
cin>>u>>d>>r>>l>>k>>p;
int ys,xs,yt,xt;
cin>>ys>>xs>>yt>>xt;
ys--;xs--;yt--;xt--;
auto C=read<string>(h);
map<int, ll> cost;
cost[-w]=u;
cost[+w]=d;
cost[+1]=r;
cost[-1]=l;
Grid G(h,w,[&](int y,int x){return C[y][x];});
Dijkstra<ll> D(h*w);
for(auto[a,b]:G.edges()){
if(G[a]=='#' or G[b]=='#') continue;
D.add_edge(a,b,cost[b-a]+p*(G[b]=='@'));
D.add_edge(b,a,cost[a-b]+p*(G[a]=='@'));
}
D.build(G.idx(ys,xs));
cout<<(D[G.idx(yt,xt)]<=k?"Yes":"No")<<endl;
return 0;
}
#line 1 "test/yukicoder/6680.test.cpp"
// verification-helper: PROBLEM https://yukicoder.me/problems/6680
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
#line 1 "io/single.cpp"
#line 3 "io/single.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T=int>
vector<T> read(size_t n){
vector<T> ts(n);
for(size_t i=0;i<n;i++) cin>>ts[i];
return ts;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
return 0;
}
#endif
#line 1 "graph/grid.cpp"
#line 3 "graph/grid.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename F>
struct Grid{
const int h,w;
const F f;
Grid(int h_,int w_,F f_):h(h_),w(w_),f(f_){}
int idx(int y,int x){return y*w+x;}
using T = typename invoke_result<F, int, int>::type;
T operator[](int k){return f(k/w,k%w);}
decltype(auto) edges(){
vector<pair<int, int>> es;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(i+1<h) es.emplace_back(idx(i,j),idx(i+1,j));
if(j+1<w) es.emplace_back(idx(i,j),idx(i,j+1));
}
}
return es;
}
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
return 0;
}
#endif
#line 1 "graph/dijkstra.cpp"
#line 3 "graph/dijkstra.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct Dijkstra{
struct Edge{
int to;
T cost;
Edge(int to,T cost):to(to),cost(cost){}
bool operator<(const Edge &o)const{return cost>o.cost;}
};
vector< vector<Edge> > G;
vector<T> ds;
vector<int> bs;
Dijkstra(int n):G(n){}
void add_edge(int u,int v,T c){
G[u].emplace_back(v,c);
}
void build(int s){
int n=G.size();
ds.assign(n,numeric_limits<T>::max());
bs.assign(n,-1);
priority_queue<Edge> pq;
ds[s]=0;
pq.emplace(s,ds[s]);
while(!pq.empty()){
auto p=pq.top();pq.pop();
int v=p.to;
if(ds[v]<p.cost) continue;
for(auto e:G[v]){
if(ds[e.to]>ds[v]+e.cost){
ds[e.to]=ds[v]+e.cost;
bs[e.to]=v;
pq.emplace(e.to,ds[e.to]);
}
}
}
}
T operator[](int k){return ds[k];}
vector<int> restore(int to){
vector<int> res;
if(bs[to]<0) return res;
while(~to) res.emplace_back(to),to=bs[to];
reverse(res.begin(),res.end());
return res;
}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
return 0;
}
#endif
#line 10 "test/yukicoder/6680.test.cpp"
#undef call_from_test
signed main(){
using ll = long long;
cin.tie(0);
ios::sync_with_stdio(0);
int h,w;
cin>>h>>w;
ll u,d,r,l,k,p;
cin>>u>>d>>r>>l>>k>>p;
int ys,xs,yt,xt;
cin>>ys>>xs>>yt>>xt;
ys--;xs--;yt--;xt--;
auto C=read<string>(h);
map<int, ll> cost;
cost[-w]=u;
cost[+w]=d;
cost[+1]=r;
cost[-1]=l;
Grid G(h,w,[&](int y,int x){return C[y][x];});
Dijkstra<ll> D(h*w);
for(auto[a,b]:G.edges()){
if(G[a]=='#' or G[b]=='#') continue;
D.add_edge(a,b,cost[b-a]+p*(G[b]=='@'));
D.add_edge(b,a,cost[a-b]+p*(G[a]=='@'));
}
D.build(G.idx(ys,xs));
cout<<(D[G.idx(yt,xt)]<=k?"Yes":"No")<<endl;
return 0;
}