#include <algorithm> #include <iostream> #include <vector> #include <queue> #include <tuple> using namespace std; template <typename T> struct Edge { int src, dst; T cost; Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { } Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { } }; template <typename T> using Edges = vector<Edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; template <typename T> using Matrix = vector<vector<T>>; template <typename T> vector<T> dijkstra(const WeightedGraph<T> &g, int s) { const T INF = numeric_limits<T>::max(); vector<T> dist(g.size(), INF); vector<int> prev(g.size(), -1); using Pi = pair<T, int>; priority_queue<Pi, vector<Pi>, greater<Pi>> que; dist[s] = 0; que.emplace(dist[s], s); while (!que.empty()) { T cost; int u; tie(cost, u) = que.top(); que.pop(); if (dist[u] < cost) continue; for (auto &e: g[u]) { int v = e.dst; T nc = e.cost; if (dist[v] <= dist[u] + nc) continue; dist[v] = dist[u] + nc; prev[v] = u; que.emplace(dist[v], v); } } return dist; } int main() { int n, v, oi, oj; cin >> n >> v >> oj >> oi; oi--, oj--; WeightedGraph<int> g(n * n); auto idx = [&](int i, int j) { return i * n + j; }; auto out_field = [&](int i, int j) { return i < 0 || i >= n || j < 0 || j >= n; }; int dij[] = {0, 1, 0, -1, 0}; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { int cost; cin >> cost; for (int k = 0; k < 4; k++) { int ni = i + dij[k], nj = j + dij[k + 1]; if (out_field(ni, nj)) continue; g[idx(ni, nj)].emplace_back(idx(i, j), cost); } } auto dist_s = dijkstra(g, idx(0, 0)); bool ok = dist_s[idx(n - 1, n - 1)] < v; if (oi != -1 && oj != -1) { auto dist_o = dijkstra(g, idx(oi, oj)); ok |= dist_o[idx(n - 1, n - 1)] < 2 * (v - dist_s[idx(oi, oj)]); } if (ok) cout << "YES" << endl; else cout << "NO" << endl; return 0; }