#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() /* No.20 砂漠のオアシス 幅優先探索 ポイントは始点 → 終点 から始めるのではなくて、終点 → 始点 から始める。 オアシスがあってもオアシスがなくても、次の街に行ける場合は 結果は YES。 いけない場合は、 オアシスがない場合 結果は NO。 オアシスがある場合 オアシス → 始点 でまずオアシスに行き着くかどうかを判定。 行きつける場合は 終点 → オアシスで オアシスに行き着いたときの体力を考慮する。 */ using namespace std; typedef long long ll; typedef pair P; typedef pair PI; const int MAX_N = 505; const int dr[] = {-1, 0, 1, 0 }; const int dc[] = { 0, 1, 0,-1 }; int desert[MAX_N][MAX_N]; int visit[MAX_N][MAX_N]; int N, V; bool bfs (int sr, int sc, int tr, int tc ){ memset (visit, -1, sizeof (visit ) ); visit[sr][sc] = 0; queue que; que.push (PI( P (sr, sc ), 0 ) ); while (!que.empty() ){ PI curr = que.front(); que.pop(); int cr = curr.first.first; int cc = curr.first.second; int cv = curr.second; rep (k, 4 ){ int nr = cr + dr[k]; int nc = cc + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= N ) continue; if (visit[nr][nc] != -1 && visit[nr][nc] <= cv + desert[cr][cc] ) continue; que.push (PI (P (nr, nc ), cv + desert[cr][cc] ) ); visit[nr][nc] = cv + desert[cr][cc]; } // end rep } // end while return (visit[tr][tc] < V ); } int main() { memset (desert, 0, sizeof (desert ) ); 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]; bool res = false; // オアシスがなくても行き着く? res |= bfs (N-1, N-1, 0, 0 ); if (!res && Ox != -1 && Oy != -1 ){ // オアシスに行き着く? bool curr = bfs (Oy, Ox, 0, 0 ); if (curr ){ V = 2*(V - visit[0][0] ); res |= bfs (N-1, N-1, Oy, Ox ); } // end if } // end if cout << (res ? "YES" : "NO" ) << endl; return 0; }