#include #include #include #include #include #include #include #include #include // require sort next_permutation count __gcd reverse etc. #include // require abs exit atof atoi #include // require scanf printf #include #include // require accumulate #include // require fabs #include #include #include #include // require setw #include // require stringstream #include // require memset #include // require tolower, toupper #include // require freopen #include // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() #define INF (10*505*505) /* No.20 砂漠のオアシス SPFA 幅優先探索とか、ダイクストラ法と呼ぶにはちょっと違う格子点平面上の最短経路探索。 幅優先探索では queue を使うが SPFA では priority_queue を使うのが 一般的。 幅優先探索でも、解くことができるが O(N^2) とはならず、データ依存? SPFA は O(N^2 log N ) かな? */ using namespace std; typedef long long ll; typedef pair P; const int MAX_N = 505; const int dr[] = {-1, 0, 1, 0 }; const int dc[] = { 0, 1, 0,-1 }; int d[MAX_N][MAX_N]; int desert[MAX_N][MAX_N]; int N, V; void spfa (void ){ rep (i, N ) rep (j, N ) d[i][j] = INF; d[0][0] = 0; priority_queue, greater

> que; que.push (P (0, 0*N + 0 ) ); while (!que.empty() ){ P curr = que.top(); que.pop(); int cost = curr.first; int cr = curr.second/N; int cc = curr.second%N; rep (k, 4 ){ int nr = cr + dr[k]; int nc = cc + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= N ) continue; if (d[nr][nc] <= cost + desert[nr][nc] ) continue; que.push ( P (cost + desert[nr][nc], nr*N + nc ) ); d[nr][nc] = cost + desert[nr][nc]; } // end rep } // end whlie } void disp (void ){ rep (i, N ){ rep (j, N ){ cerr << setw(2) << (d[i][j] == INF ? -1 : d[i][j] ); } // end rep cerr << endl; } // end rep cerr << endl; } int main() { ios_base::sync_with_stdio(0); int Ox, Oy; cin >> N >> V >> Ox >> Oy; Ox--, Oy--; rep (i, N ) rep (j, N ) cin >> desert[i][j]; spfa(); bool res = false; // オアシスがなくても行き着く? res |= (d[N-1][N-1] < V ); // disp (); if (!res && Ox != -1 && Ox != -1 ){ res |= (d[Oy][Ox] < V ); if (res ){ V = 2*(V - d[Oy][Ox] ); res |= (d[N-1][N-1] < V ); } // end if } // end if cout << (res ? "YES" : "NO" ) << endl; return 0; }