#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; int spfa (int sy, int sx, int ey, int ex ){ rep (i, N ) rep (j, N ) d[i][j] = INF; d[sy][sx] = 0; priority_queue, greater

> que; que.push (P (0, sy*N + sx ) ); 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]; int ncost = cost + desert[nr][nc]; if (nr < 0 || nr >= N || nc < 0 || nc >= N ) continue; if (d[nr][nc] > ncost ){ que.push ( P (ncost, nr*N + nc ) ); d[nr][nc] = ncost; } // end if } // end rep } // end whlie return d[ey][ex]; } 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[j][i]; // オアシスがなくても行き着く? int ans = spfa (0, 0, N - 1, N - 1 ); bool res = (ans < V ); // disp (); if (!res && Ox != -1 && Ox != -1 ){ ans = spfa (0, 0, Oy, Ox ); if (ans < V ){ V = 2*(V - d[Oy][Ox] ); ans = spfa (Oy, Ox, N - 1, N - 1 ); res |= (ans < V ); } // end if } // end if cout << (res ? "YES" : "NO" ) << endl; return 0; }