#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define SUM(a) accumulate(ALL(a), 0) #define array2(type, x, y) array, x> #define vector2(type) vector > #define out(...) printf(__VA_ARGS__) typedef pair pos; int pos::*x = &pos::first; int pos::*y = &pos::second; int dxy[] = {0, 1, 0, -1, 0}; /*================================*/ int N, V; pos oasis; int m[200][200]; int cost(pos s, pos g) { int c[200][200]; REP(x,N) REP(y,N) c[x][y] = 1e10; queue que; que.push(s); c[s.*x][s.*y] = 0; while(que.size()) { pos p = que.front(); que.pop(); REP(i,4) { int nx = p.*x + dxy[i]; int ny = p.*y + dxy[i+1]; if (nx<0||N<=nx||ny<0||N<=ny) continue; int cost = c[p.*x][p.*y] + m[nx][ny]; if (cost < c[nx][ny]) { c[nx][ny] = cost; que.push(pos(nx,ny)); } } } return c[g.*x][g.*y]; } signed main() { cin >> N >> V >> oasis.*x >> oasis.*y; oasis.*x -= 1; oasis.*y -= 1; REP(y,N) REP(x,N) cin >> m[x][y]; // ダイクストラでゴールまでのコストを算出 int gc = cost(pos(0,0), pos(N-1,N-1)); if (V - gc <= 0) { if (oasis.*x == 0 && oasis.*y == 0) { cout << "NO" << endl; return 0; } int oc = cost(pos(0,0), oasis); int ogc = cost(oasis, pos(N-1,N-1)); if (V - oc <= 0 || (V - oc) * 2 - ogc <= 0) { cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0; }