#include #define FOR(i, a, b) for (ll i = (a); i < (b); i++) #define RFOR(i, a, b) for (ll i = (b)-1; i >= (a); i--) #define rep(i, n) for (ll i = 0; i < (n); i++) #define rep1(i, n) for (ll i = 1; i <= (n); i++) #define rrep(i, n) for (ll i = (n)-1; i >= 0; i--) #define pb push_back #define mp make_pair #define fst first #define snd second #define show(x) cout << #x << " = " << x << endl #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) #define pii pair #define vi vector using namespace std; template ostream& operator<<(ostream& o, const pair& p) { return o << "(" << p.first << "," << p.second << ")"; } template ostream& operator<<(ostream& o, const vector& vc) { o << "sz = " << vc.size() << endl << "["; for (const T& v : vc) o << v << ","; o << "]"; return o; } using ll = long long; constexpr ll MOD = 1000000007; struct Edge { Edge(int to, int cost) : to{to}, cost{cost} {} int to; int cost; }; class Graph { public: Graph(int v) : m_v{v} { m_table.resize(v); } void addEdge(int to, int from, int cost) { m_table[to].pb(Edge{from, cost}); } void Dijkstra(const std::size_t s, std::vector& d) const { assert(s < m_v); assert(d.size() == m_v); using P = std::pair; std::priority_queue, std::greater

> q; for (std::size_t i = 0; i < m_v; i++) { d[i] = INF; } d[s] = 0; q.push(std::make_pair(0, s)); while (not q.empty()) { const P& p = q.top(); const int cost = p.first; const std::size_t v = p.second; q.pop(); if (d[v] < cost) { continue; } for (const auto& e : m_table[v]) { if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; q.push(std::make_pair(d[e.to], e.to)); } } } } static constexpr int INF = numeric_limits::max() / 100; private: int m_v; vector> m_table; }; int N; inline int encode(int i, int j) { return i * N + j; } inline pii decode(int n) { return mp(n / N, n % N); } int main() { int V, Ox, Oy; cin >> N >> V >> Ox >> Oy; Graph g{N * N}; vector> level(N, vector(N)); for (int j = 0; j < N; j++) { for (int i = 0; i < N; i++) { cin >> level[i][j]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i > 0) { g.addEdge(encode(i - 1, j), encode(i, j), level[i][j]); } if (i < N - 1) { g.addEdge(encode(i + 1, j), encode(i, j), level[i][j]); } if (j > 0) { g.addEdge(encode(i, j - 1), encode(i, j), level[i][j]); } if (j < N - 1) { g.addEdge(encode(i, j + 1), encode(i, j), level[i][j]); } } } const int s = 0; const int t = N * N - 1; if (Ox == 0 and Oy == 0) { vector d(N * N); g.Dijkstra(s, d); const int di = d[t]; if (V <= di) { cout << "NO" << endl; } else { cout << "YES" << endl; } } else { Ox--; Oy--; const int oasis = encode(Ox, Oy); vector d(N * N); g.Dijkstra(s, d); if (V > d[t]) { cout << "YES" << endl; return 0; } const int di1 = d[oasis]; if (V <= di1) { cout << "NO" << endl; } else { V = (V - di1) * 2; g.Dijkstra(oasis, d); const int di2 = d[t]; if (V <= di2) { cout << "NO" << endl; } else { cout << "YES" << endl; } } } return 0; }