/* -*- coding: utf-8 -*- * * 20.cc: No.20 砂漠のオアシス - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 200; const int INF = 1 << 30; const int dxs[] = {1, 0, -1, 0}, dys[] = {0, -1, 0, 1}; /* typedef */ struct Stat { int d, x, y; Stat() {} Stat(int _d, int _x, int _y): d(_d), x(_x), y(_y) {} bool operator<(const Stat &s) const { return d > s.d; } }; /* global variables */ int ls[MAX_N][MAX_N], dists[MAX_N][MAX_N]; /* subroutines */ void dijkstra(int n, int sx, int sy, int dists[MAX_N][MAX_N]) { for (int y = 0; y < n; y++) for (int x = 0; x < n; x++) dists[y][x] = INF; dists[sy][sx] = 0; priority_queue q; q.push(Stat(0, sx, sy)); while (! q.empty()) { Stat u = q.top(); q.pop(); if (dists[u.y][u.x] != u.d) continue; for (int di = 0; di < 4; di++) { int vx = u.x + dxs[di], vy = u.y + dys[di]; if (vx >= 0 && vx < n && vy >= 0 && vy < n) { int vd = u.d + ls[vy][vx]; if (dists[vy][vx] > vd) { dists[vy][vx] = vd; q.push(Stat(vd, vx, vy)); } } } } } /* main */ int main() { int n, v, ox, oy; cin >> n >> v >> ox >> oy; ox--, oy--; for (int y = 0; y < n; y++) for (int x = 0; x < n; x++) cin >> ls[y][x]; dijkstra(n, 0, 0, dists); if (v > dists[n - 1][n - 1]) { puts("YES"); return 0; } if (ox >= 0 && oy >= 0) { int d0 = dists[oy][ox]; if (v > d0) { int v0 = (v - d0) * 2; dijkstra(n, ox, oy, dists); if (v0 > dists[n - 1][n - 1]) { puts("YES"); return 0; } } } puts("NO"); return 0; }