#pragma GCC optimize ("O3") // #pragma GCC optimize ("O2") 以下で自動ベクトル化を行う場合は、#pragma GCC optimize ("tree-vectorize") も合わせて記述してください。 #pragma GCC target ("avx") // ターゲットの変更 sse4, avx, avx2 など #include using namespace std; typedef long long ll; typedef pair< int, int > pii; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef vector< pii > vp; typedef vector< vp > vvp; typedef vector< string > vs; typedef vector< double > vd; typedef vector< vd > vvd; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; const string msg[] = { "NO", "YES" }; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; int N, V, Ox, Oy; vvi L; void init(){ cin >> N >> V >> Ox >> Oy; L = vvi( N, vi( N ) ); for( int i = 0; i < N; ++i ) for( int j = 0; j < N; ++j ) cin >> L[ i ][ j ]; } typedef vector< vvi > vvvi; typedef vector< vvvi > vvvvi; vvvvi dp; int in_range( int n, int x, int y ){ return 0 <= x and x < n and 0 <= y and y < n; } void preprocess(){ if( V <= L[ 0 ][ 0 ] ) cout << msg[ 0 ] << endl, exit( 0 ); dp = vvvvi( 2 * V + 1, vvvi( N, vvi( N, vi( 2 ) ) ) ); dp[ V - L[ 0 ][ 0 ] ][ 0 ][ 0 ][ 0 ] = 1; queue< tuple< int, int, int, int > > que; que.emplace( V, 0, 0, 0 ); while( not que.empty() ){ int v, x, y, t; tie( v, x, y, t ) = que.front(); que.pop(); // cout << "dp[ " << v << " ][ " << x << " ][ " << y << " ][ " << t << " ] = " << dp[ v ][ x ][ y ][ t ] << endl; int nv = v; int nt = t; if( x + 1 == Ox and y + 1 == Oy and not t ) nv *= 2, nt = 1; for( int di = 0; di < 4; ++di ){ int nx = x + dx[ di ]; int ny = y + dy[ di ]; if( not in_range( N, nx, ny ) ) continue; if( nv - L[ nx ][ ny ] > 0 ) if( upmax( dp[ nv - L[ nx ][ ny ] ][ nx ][ ny ][ nt ], dp[ v ][ x ][ y ][ t ] ) ) que.emplace( nv - L[ nx ][ ny ], nx, ny, nt ); } } } void solve(){ for( int i = 1; i <= 2 * V; ++i ) for( int j = 0; j < 2; ++j ) if( dp[ i ][ N - 1 ][ N - 1 ][ j ] ) cout << msg[ 1 ] << endl, exit( 0 ); cout << msg[ 0 ] << endl; } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }