#include #define endl '\n' #define int long long #define lint long long #define pii pair #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define SZ(v) ((int)v.size()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define MINF(a) memset(a,0x3f,sizeof(a)) #define POW(n) (1LL<<(n)) #define POPCNT(n) (__builtin_popcount(n)) #define IN(i,a,b) (a <= i && i <= b) using namespace std; template inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; } template inline bool CHMAX(T& a,T b) { if(a inline void SORT(T& a) { sort(ALL(a)); } template inline void REV(T& a) { reverse(ALL(a)); } template inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); } template inline T LB(vector& v, T a) { return *lower_bound(ALL(v),a); } template inline int LBP(vector& v, T a) { return lower_bound(ALL(v),a) - v.begin(); } template inline T UB(vector& v, T a) { return *upper_bound(ALL(v),a); } template inline int UBP(vector& v, T a) { return upper_bound(ALL(v),a) - v.begin(); } template ostream& operator<< (ostream& os, const pair& p) { os << p.first << " " << p.second; return os; } template istream& operator>> (istream& is, pair& p) { is >> p.first >> p.second; return is; } template ostream& operator<< (ostream& os, const vector& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; } template istream& operator>> (istream& is, vector& v) { for(T& in : v) is >> in; return is; } template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, Ts... ts) { return vector(ts...))>(a,make_v(ts...)); } template typename enable_if::value == 0>::type fill_v(T &t, const V &v) { t = v; } template typename enable_if::value != 0>::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e,v); } const lint MOD = 1000000007; const lint INF = 0x3f3f3f3f3f3f3f3f; const double EPS = 1e-10; const int dy[] = {-1, 0, 0, 1}; const int dx[] = {0, -1, 1, 0}; int N, V; int ox, oy; int L[210][210]; int dis[2][210][210]; bool inQue[210][210]; queue que; void SPFA(int idx, int sy, int sx) { MINF(dis[idx]); REP(i, N) REP(j, N) inQue[i][j] = false; dis[idx][sy][sx] = 0; que.emplace(sy, sx); inQue[sy][sx] = true; while (!que.empty()) { int y, x; tie(y, x) = que.front(); que.pop(); inQue[y][x] = false; REP(i, 4) { int ny = y + dy[i]; int nx = x + dx[i]; if (IN(ny, 0, N - 1) && IN(nx, 0, N - 1)) { if (CHMIN(dis[idx][ny][nx], dis[idx][y][x] + L[ny][nx]) && !inQue[ny][nx]) { que.emplace(ny, nx); inQue[ny][nx] = true; } } } } } void _main() { cin >> N >> V >> ox >> oy; ox--; oy--; REP(i, N) REP(j, N) cin >> L[i][j]; SPFA(0, 0, 0); bool yes = (dis[0][N - 1][N - 1] < V); if (ox >= 0 && oy >= 0) { SPFA(1, oy, ox); yes |= (dis[1][N - 1][N - 1] < 2 * (V - dis[0][oy][ox])); } cout << (yes ? "YES" : "NO") << endl; } signed main(signed argc, char **argv) { if (argc > 1) { if (strchr(argv[1], 'i')) freopen("input.txt", "r", stdin); if (strchr(argv[1], 'o')) freopen("output.txt", "w", stdout); } cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); _main(); return 0; }