module main; // https://yang33-kassa.jp/yukicoder/yukicoder020/ より // 2次元グリッド、ダイクストラ法 import std; int N, V, Oy, Ox; immutable INF = 10 ^^ 9; // C++ の tie auto tie(StoreElements...)(ref StoreElements stores) { alias Elements = staticMap!(Unqual, StoreElements); template toPointer(T) { alias toPointer = T*; } struct Holder { alias StoreElementsPtrs = staticMap!(toPointer, StoreElements); StoreElementsPtrs storePtrs; this(ref StoreElements stores) { foreach(i, _; StoreElements) { storePtrs[i] = &stores[i]; } } void opAssign(Tuple!Elements values) { foreach(i, _; Elements) { *storePtrs[i] = values[i]; } } } return Holder(stores); } auto dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]; int[][] dijkstra(int sy, int sx, int[][] cost) { alias T = Tuple!(int, int, int); auto dist = uninitializedArray!(int[][])(N, N); foreach (ref row; dist) row[] = INF; dist[sy][sx] = 0; auto que = redBlackTree!("a[0] < b[0]", true, T)(T(0, sy, sx)); while (!que.empty) { int d, y, x; tie(d, y, x) = que.front; que.removeFront; if (dist[y][x] < d) continue; foreach (di; dir) { int ny = y + di[0], nx = x + di[1]; if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue; if (dist[ny][nx] > dist[y][x] + cost[ny][nx]) { dist[ny][nx] = dist[y][x] + cost[ny][nx]; que.insert(T(dist[ny][nx], ny, nx)); } } } return dist; } void main() { // 入力 readln.chomp.formattedRead("%d %d %d %d", N, V, Ox, Oy); --Oy, --Ox; auto cost = new int[][](N); foreach (ref row; cost) { row = readln.split.to!(int[]); } // 答えの計算と出力 auto dist = dijkstra(0, 0, cost); if (dist[N - 1][N - 1] < V) { writeln("YES"); return; } if (Oy == -1 && dist[N - 1][N - 1] >= V) { writeln("NO"); return; } int recover = 2 * (V - dist[Oy][Ox]); dist = dijkstra(Oy, Ox, cost); if (dist[N - 1][N - 1] < recover) writeln("YES"); else writeln("NO"); }