#include #include #include #include #include using namespace std; template 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 using Edges = vector>; template using WeightedGraph = vector>; template using Matrix = vector>; template vector dijkstra(const WeightedGraph &g, int s) { const T INF = numeric_limits::max(); vector dist(g.size(), INF); vector prev(g.size(), -1); using Pi = pair; priority_queue, greater> 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 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; }