#include using namespace std; using ll = long long; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b void vprint(T &V){ for(auto v : V){ cout << v << " "; } cout << endl; } struct Edge{ ll to; ll cost; Edge(ll to, ll cost): to(to), cost(cost) {} Edge(){ to = 0; cost = 0; } }; struct Node{ ll distance; ll index; Node(ll d, ll i){ distance = d; index = i; } Node(){} bool operator<(const Node &another) const { return distance < another.distance; } bool operator>(const Node &another) const { return distance > another.distance; } }; struct Dijkstra{ vector d; vector > graph; vector done; // ノード数を入れる void initialize(ll size){ d.resize(size); done.resize(size); graph.resize(size); reset(); } void reset(){ ll N = graph.size(); FOR(i, 0, N){ d[i] = inf; done[i] = false; } } ll distance(int i){ if(d.size()<=i) return -1; return d[i]; } void print_graph(){ FOR(i, 0, graph.size()){ cout << i << " -> "; for(auto edge : graph[i]){ cout << edge.to << " "; } cout << endl; } p("distance"); FOR(i, 0, graph.size()){ ll d = distance(i); cout << i << " " << d << endl; } } void register_edge(ll a, ll b, ll cost){ auto edge = Edge(b, cost); graph[a].push_back(edge); } void calc_shortest_path(ll from=0){ priority_queue, greater > que; auto node = Node(); // 始点 node.index = from; node.distance = 0; que.push(node); while(!que.empty()){ // 1番distanceが小さいノード Node n = que.top(); que.pop(); if(done[n.index]){ continue; } done[n.index] = true; d[n.index] = n.distance; auto edge_list = graph[n.index]; for(auto edge : edge_list){ // 短くなるノードがあれば if(!done[edge.to] && n.distance + edge.cost < d[edge.to]){ ll shorter_distance = n.distance + edge.cost; que.push(Node(shorter_distance, edge.to)); } } } } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N, V, Ox, Oy; cin >> N >> V >> Ox >> Oy; Ox--; Oy--; vector > A(N); FOR(i, 0, N){ FOR(j, 0, N){ ll L; cin >> L; A[i].push_back(L); } } auto dij = Dijkstra(); dij.initialize(N*N); // よこ FOR(y, 0, N){ FOR(x, 0, N-1){ ll cost0 = A[y][x]; ll cost1 = A[y][x+1]; ll index = N*y + x; dij.register_edge(index, index+1, cost1); dij.register_edge(index+1, index, cost0); } } // たて FOR(x, 0, N){ FOR(y, 0, N-1){ ll cost0 = A[y][x]; ll cost1 = A[y+1][x]; ll index = N*y + x; dij.register_edge(index, index+N, cost1); dij.register_edge(index+N, index, cost0); } } dij.calc_shortest_path(); ll d = dij.distance(N*N-1); ll rest_HP = V - d; if(rest_HP>0){ p_yes(); return 0; } // 直行できなかった場合は以下 // オアシスがない if(Ox==-1 && Oy==-1){ p_no(); return 0; } d = dij.distance(N*Oy + Ox); rest_HP = V - d; if(rest_HP<=0){ p_no(); return 0; } rest_HP *= 2; // オアシス dij.reset(); dij.calc_shortest_path(N*Oy + Ox); d = dij.distance(N*N-1); if(rest_HP-d>0){ p_yes(); }else{ p_no(); } return 0; }