#include #define ll long long #define INF 1e9 #define LINF 1e18 #define rep(i,n) for(int i=0;i P; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; typedef struct Edge { ll to,cost; } Edge; vector> g; int L[222][222]; void print(const vector &dp, int n) { rep(i,n) { rep(j,n) { cout << i*n+j << " "; } cout << endl; } } void make_graph(int n, int m) { rep(i,n) { rep(j,m) { rep(k,4) { int now = i*n+j; int nx = i+dx[k]; int ny = j+dy[k]; if (-1 < nx && nx < n && -1 < ny && ny < m) { // printf("now = %d, nx = %d, ny = %d\n", now,nx,ny); int cost = L[nx][ny]; int to = nx*n+ny; g[now].push_back(Edge{to,cost}); } } } } } void dijkstra(vector &dp, int s) { priority_queue, greater

> pq; pq.push({0,s}); dp[s] = 0; while (!pq.empty()) { P p = pq.top(); pq.pop(); int v = p.second; for (auto &&e: g[v]) { if (dp[e.to] > dp[v]+e.cost) { dp[e.to] = dp[v]+e.cost; pq.push({dp[e.to], e.to}); } } } } int main() { int n,v,ox,oy; cin >> n >> v >> ox >> oy; --ox, --oy; g.resize(n*n); rep(i,n) rep(j,n) cin >> L[i][j]; make_graph(n,n); vector dp(n*n, INF); dijkstra(dp,0); int goal = n*n-1; if (v-dp[goal] > 0) { cout << "YES" << endl; return 0; } if (ox == -1 && oy == -1) { cout << "NO" << endl; return 0; } int oasis = oy*n+ox; int oasis_v = v-dp[oasis]; oasis_v *= 2; dp.assign(n*n,INF); dijkstra(dp,oasis); if (oasis_v-dp[goal] > 0) { cout << "YES" << endl; return 0; } cout << "NO" << endl; return 0; }