#define _USE_MATH_DEFINES #include #include #include #include #include //#include #include #include #include #include #include #include ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)< ///////// typedef long long LL; typedef long double LD; ///////// using namespace::std; ///////// const int V = 160000,INF = 1<<28; int dist[200][200]; bool use[200][200]; int dist2[200][200]; bool use2[200][200]; int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// //cout << setprecision(10);// int N,V,Ox,Oy; cin>>N>>V>>Ox>>Oy; --Ox; --Oy; int L[200][200]; rep(i,N)rep(j,N){ cin>>L[i][j];//y,x } int dx[4] = { 1, 0,-1, 0}; int dy[4] = { 0, 1, 0,-1}; int px,py,nx,ny,atV; rep(i,200)rep(j,200){ dist[i][j] = INF; dist2[i][j] = INF; } //priority_queue,greater > q; priority_queue,greater > q[5]; PII temp; //q.push( PII(0,0) ); q[0].push( PII(0,0) ); while( !q[0].empty() || !q[1].empty() || !q[2].empty() || !q[3].empty() || !q[4].empty() ) //while( !q.empty() ) { rep(i,5){ if( q[i].empty() == true) continue; temp = q[i].top();q[i].pop(); py = (temp.second/N); px = (temp.second%N); break; } if( use[py][px] == true) continue; use[py][px] = true; dist[py][px] = temp.first; if(temp.first >= V) break; if(use[N-1][N-1] == true && (Ox==-1 || use[Oy][Ox]==true)) break; rep(i,4){ ny = py + dy[i]; nx = px + dx[i]; if(0 <= ny && ny < N && 0 <= nx && nx < N && use[ny][nx] == false){ atV = temp.first + L[ny][nx]; q[atV/128].push( PII( atV, ny*N+nx) ); } } } if(dist[N-1][N-1] < V){ P("YES"); return 0; } if( (Ox != -1 || Oy != -1) && dist[Oy][Ox] < V) { //rep(i,N)rep(j,N)use[i][j] = false; //priority_queue,greater > q2[5]; priority_queue,greater > q2[5]; q2[0].push( PII( 0, Oy*N+Ox) ); //while( !q2.empty() ) while( !q2[0].empty() || !q2[1].empty() || !q2[2].empty() || !q2[3].empty() || !q2[4].empty() ) { rep(i,5){ if( q2[i].empty() == true) continue; temp = q2[i].top();q2[i].pop(); py = (temp.second/N); px = (temp.second%N); break; } if( use2[py][px] == true) continue; use2[py][px] = true; dist2[py][px] = temp.first; if( temp.first >= (V-dist[Oy][Ox])*2 ){ break; } if(use2[N-1][N-1]==true){ break; } rep(i,4){ ny = py + dy[i]; nx = px + dx[i]; if(0 <= ny && ny < N && 0 <= nx && nx < N && use2[ny][nx] == false){ atV = temp.first + L[ny][nx]; q2[atV/200].push( PII( atV, ny*N+nx) ); } } } if( dist[Oy][Ox] < V && dist2[N-1][N-1] < (V-dist[Oy][Ox])*2 ){ P("YES"); return 0; } } P("NO"); return 0; }