// #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; using namespace atcoder; using mint = modint998244353; // using mint = modint1000000007; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair; using pll = pair; using T = tuple; using G = vector>; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep2(i, a, b) for (ll i = a; i < (b); ++i) #define rrep2(i, a, b) for (ll i = a-1; i >= (b); --i) #define rep3(i, a, b, c) for (ll i = a; i < (b); i+=c) #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define popcount __builtin_popcount #define popcountll __builtin_popcountll #define fi first #define se second #define UNIQUE(v) sort(rng(v)), v.erase(unique(rng(v)), v.end()) #define MIN(v) *min_element(rng(v)) #define MAX(v) *max_element(rng(v)) template bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,T b){if(a void printv(vector &v){rep(i,v.size())cout< void printvv(vector> &v){rep(i,v.size())rep(j,v[i].size())cout<> n >> h; int ox, oy; cin >> oy >> ox; ox--, oy--; vector> g(n*n); rep(i, n)rep(j, n){ int w; cin >> w; rep(t, 4){ int ni = i+dx[t], nj = j+dy[t]; if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue; g[ni*n+nj].emplace_back(i*n+j, w); } } auto dijkstra = [&](int sx, int sy, int gx, int gy, int &h, int f)-> bool{ vector dist(n*n, INF); dist[sx*n+sy] = 0; priority_queue, greater> pq; pq.emplace(0, sx*n+sy); while(!pq.empty()){ auto [c, u] = pq.top(); pq.pop(); if (dist[u] < c) continue; for(auto [v, w]: g[u]){ if (dist[v] > dist[u]+w && dist[u]+w < h){ dist[v] = dist[u]+w; pq.emplace(dist[v], v); } } } if (f) h -= dist[gx*n+gy]; return dist[gx*n+gy] != INF; }; if (dijkstra(0, 0, n-1, n-1, h, 0)){ cout << "YES" << endl; return 0; } if (ox != -1){ if (!dijkstra(0, 0, ox, oy, h, 1)){ cout << "NO" << endl; return 0; } h *= 2; if (dijkstra(ox, oy, n-1, n-1, h, 1)){ cout << "YES" << endl; return 0; } } cout << "NO" << endl; return 0; }