#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for(ll i = 0;i < n;i++) #define REPR(i, n) for(ll i = n;i >= 0;i--) #define FOR(i, m, n) for(ll i = m;i < n;i++) #define FORR(i, m, n) for(ll i = m;i >= n;i--) #define REPO(i, n) for(ll i = 1;i <= n;i++) #define ll long long #define INF (ll)1 << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(),n.end() #define MOD 1000000007 #define P pair ll n, v, ox, oy, o, s[110000]; ll d[110000]; // 結果 bool ok = false; struct edge { ll to, cost; }; vector g[110000]; //隣接リスト to, cost void dijkstra(ll a) { priority_queue, greater

> q; fill(d, d + n * n, INF); d[a] = 0; q.push(P(0, a)); while (!q.empty()) { P p = q.top(); q.pop(); ll v = p.second; if (d[v] < p.first) continue; REP(i, g[v].size()) { edge e = g[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; q.push(P(d[e.to], e.to)); } } } } ll v1[4] = { 0,0,1,-1 }, v2[4] = { 1,-1,0,0 }; int main() { cin >> n >> v >> ox >> oy; ox--; oy--; o = oy * n + ox; REP(i, n) { REP(j, n) { cin >> s[i * n + j]; } } REP(i, n) { REP(j, n) { REP(k, 4) { if ((j == n - 1 and v2[k] == 1) or (j == 0 and v2[k] == -1))continue; ll now = i * n + j + v1[k] * n + v2[k]; if (now < 0 or now >= n * n)continue; g[i * n + j].push_back({ now, s[now] }); } } } dijkstra(0); if (d[n * n - 1] < v)ok = true; if (o >= 0) { v = (v - d[o]) * 2; dijkstra(o); if (d[n * n - 1] < v)ok = true; } cout << (ok ? "YES" : "NO") << endl; }