#include <iostream> #include <algorithm> #include <array> #include <cassert> #include <tuple> #include <queue> using namespace std; constexpr int inf = 987654321; // N E S W constexpr array<int, 4> dr = {-1, 0, 1, 0}, dc = { 0, 1, 0,-1}; constexpr int dr_size = dr.size(); int N, V, Oc, Or; vector<vector<int>> G, cost; void dijk(vector<vector<int>> &cost, int sr, int sc, int V) { cost.assign(N, vector<int>(N, inf)); // cost[座標] := ダメージ量 cost[sr][sc] = 0; priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; pq.emplace(0, sr, sc); while(!pq.empty()) { int dm, r, c; tie(dm, r, c) = pq.top(); pq.pop(); if(dm == V) { continue; } for(int i=0; i<dr_size; ++i) { int nr = r + dr[i], nc = c + dc[i]; if(!(0 <= nr && nr < N && 0 <= nc && nc < N)) { continue; } if(cost[nr][nc] > cost[r][c] + G[nr][nc]) { cost[nr][nc] = cost[r][c] + G[nr][nc]; pq.emplace(cost[nr][nc], nr, nc); } } } } int main(void) { scanf("%d%d%d%d", &N, &V, &Oc, &Or); assert(2 <= N && N <= 200); assert(1 <= V && V <= 500); assert((1 <= Or && Or <= N && 1 <= Oc && Oc <= N) || (Or == 0 && Oc == 0)); --Or, --Oc; G.assign(N, vector<int>(N, 0)); for(int r=0; r<N; ++r) { for(int c=0; c<N; ++c) { scanf("%d", &G[r][c]); assert(0 <= G[r][c] && G[r][c] <= 9); } } dijk(cost, 0, 0, V); if(cost[N-1][N-1] < V) { puts("YES"); return 0; } // オアシスがあってそこまで辿りつける if(Or != -1 && Oc != -1 && cost[Or][Oc] < V) { int nV = (V - cost[Or][Oc]) * 2; dijk(cost, Or, Oc, nV); if(cost[N-1][N-1] < nV) { puts("YES"); return 0; } } puts("NO"); return 0; }