#include #include #include #include #include #include #include #define rep(i, n) for (int i = 0; i < (n); i++) #define rrep(i, n) for (int i = (n)-1; i >= 0; i--) using namespace std; typedef long long int lli; lli MOD = 1000000000000000007; int f[205][205]; int n; int v, ox, oy; bool inrange(int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; } struct node { lli d, x, y; }; int vx[] = {1, 0, -1, 0}; int vy[] = {0, 1, 0, -1}; int main() { cin >> n >> v >> ox >> oy; ox--, oy--; lli dis[205][205] = {}; auto comp = [](const node l, const node r) -> bool { return l.d < r.d; }; rep(i, n) rep(j, n) cin >> f[i][j]; { priority_queue, decltype(comp)> que(comp); que.push({f[0][0], 0, 0}); rep(i, 205) rep(j, 205) dis[i][j] = MOD; while (!que.empty()) { node cur = que.top(); que.pop(); if (dis[cur.x][cur.y] < cur.d || (dis[cur.x][cur.y] != MOD && dis[cur.x][cur.y] > v)) continue; //cout << cur.x << ' ' << cur.y << endl; dis[cur.x][cur.y] = cur.d; rep(i, 4) { int nx = cur.x + vx[i]; int ny = cur.y + vy[i]; if (inrange(nx, ny)) { if (dis[nx][ny] > cur.d + f[nx][ny]) { que.push({cur.d + f[nx][ny], nx, ny}); dis[nx][ny] = cur.d + f[nx][ny]; } } } } } if (ox == -1) { cout << (dis[n - 1][n - 1] < v ? "YES" : "NO") << endl; } else { if (dis[n - 1][n - 1] < v) { cout << "YES" << endl; return 0; } if (dis[ox][oy] < v) { v = 2 * (v - f[ox][oy]); priority_queue, decltype(comp)> que(comp); que.push({0, ox, oy}); rep(i, 205) rep(j, 205) dis[i][j] = MOD; while (!que.empty()) { node cur = que.top(); que.pop(); if (dis[cur.x][cur.y] < cur.d || (dis[cur.x][cur.y] != MOD && dis[cur.x][cur.y] > v)) continue; //cout << cur.x << ' ' << cur.y << endl; dis[cur.x][cur.y] = cur.d; rep(i, 4) { int nx = cur.x + vx[i]; int ny = cur.y + vy[i]; if (inrange(nx, ny)) { if (dis[nx][ny] > cur.d + f[nx][ny]) { que.push({cur.d + f[nx][ny], nx, ny}); dis[nx][ny] = cur.d + f[nx][ny]; } } } } if (dis[n - 1][n - 1] < v) { cout << "YES" << endl; } else { cout << "NO" << endl; } } else { cout << "NO" << endl; } } }