#include #include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) typedef long long ll; using namespace std; int inputValue(){ int a; cin >> a; return a; }; void inputArray(int * p, int a){ rep(i, a){ cin >> p[i]; } }; void inputVector(vector * p, int a){ rep(i, a){ int input; cin >> input; p -> push_back(input); } } template void output(T a, int precision) { if(precision > 0){ cout << setprecision(precision) << a << "\n"; } else{ cout << a << "\n"; } } int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int cost(pair start, pair goal, vector> L, int N, int V){ vector> isVis(N, vector(N)); int ret = V; // priority_queue>, vector>>, greater>>> pq; priority_queue>> pq; pq.push(make_pair(ret, start)); while (!pq.empty()) { int v = pq.top().first; int x = pq.top().second.first; int y = pq.top().second.second; pq.pop(); if (isVis[x][y]) { continue; } isVis[x][y] = true; if (x == goal.first && y == goal.second) { ret = v; break; } rep(i, 4){ int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= N || ny < 0 || ny >= N || isVis[nx][ny] == true) { continue; } int nv = v - L[nx][ny]; pq.push(make_pair(nv, make_pair(nx, ny))); } } return ret; } int main(int argc, const char * argv[]) { // source code int N = inputValue(); // 一辺 200 int V = inputValue(); // 体力 500 pair O = make_pair(inputValue() - 1, inputValue() - 1); // オアシスの位置 vector> L(N, vector(N)); // 減る体力 rep(i, N){ rep(j, N){ L[i][j] = inputValue(); } } int costStartGoal = V - cost(make_pair(0, 0), make_pair(N - 1, N - 1), L, N, V); int costStartOasis = 1000; int costOasisGoal = 1000; if (O.first >= 0 && O.second >= 0) { costStartOasis = V - cost(make_pair(0, 0), O, L, N ,V); costOasisGoal = V - cost(O, make_pair(N - 1, N - 1), L, N, V); } if (costStartGoal < V || 2 * (V - costStartOasis) - costOasisGoal > 0) { output("YES", 0); } else{ output("NO", 0); } return 0; }