#include #define F first #define S second using namespace std; typedef pairP; typedef pairPP; priority_queue,greater >pq; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int main(){ int n,hp,ox,oy; int mas[222][222]; int dics[222][222][2];//3つ目はオアシスを使えるかどうか cin >> n >> hp >> ox >> oy; for(int i=0;i> mas[i][j]; } } if(ox==0 && oy==0){ dics[0][0][0]=hp; pq.push(PP(P(hp,0),P(0,0)));//左から体力、オアシス不可、x、y座標 }else{ dics[0][0][1]=hp; pq.push(PP(P(hp,1),P(0,0)));//左から体力、オアシス不可、x、y座標 } while(!pq.empty()){ PP now=pq.top(); pq.pop(); int sa=0,flag=now.F.S; for(int i=0;i<4;i++){ int nx,ny; nx=now.S.F + dx[i]; ny=now.S.S + dy[i]; if(nx<0 || ny<0 || nx>=n || ny>=n)continue; if(dics[now.S.S][now.S.F][flag] - mas[ny][nx] > 0){//体力が尽きずに移動できたら sa=dics[now.S.S][now.S.F][flag] - mas[ny][nx]; }else continue; /*ダイクストラの要領*/ if(dics[ny][nx][flag] < sa){//移動前後でそこの場所への最小ルートが変化しそうだったら dics[ny][nx][flag] = sa; pq.push(PP(P(sa,flag),P(nx,ny))); } /*オアシスに行く権利があり、その場所の体力最小数が今現在の体力を2倍したものより小さい*/ if(nx==ox && ny==oy && flag==1 && dics[ny][nx][1] < (2*sa)){ dics[ny][nx][0]=sa*2; pq.push(PP(P(2*sa,0),P(nx,ny))); } } } if(dics[n-1][n-1][0]>0 || dics[n-1][n-1][1]>0){ cout << "YES" << endl; }else{ cout << "NO" << endl; } }