#include #include #include #include #include #include #include using namespace std; int DIR_X[] = {-1, 1, 0, 0}; int DIR_Y[] = { 0, 0, 1, -1}; typedef vector vi; typedef vector> vvi; void dijkstra(vvi& field, vvi& cost, int sx, int sy) { cost.assign(field.size(), vi(field[0].size(), INT_MAX)); auto queue = priority_queue, vector>, greater>>(); queue.emplace(sx, sy, 0); cost[sx][sy] = 0; while(!queue.empty()) { int ix, iy, ic; tie(ix, iy, ic) = queue.top(); queue.pop(); if(ic <= cost[ix][iy]) { for(int i=0; i<4; i++) { int nx = ix + DIR_X[i]; if(nx<0 || field.size()<=nx) continue; int ny = iy + DIR_Y[i]; if(ny<0 || field[0].size()<=ny) continue; int c = ic + field[nx][ny]; if(c0 || oy>0) { int oasis_life = life - cost[ox][oy]; if(oasis_life <= 0) { printf("NO"); return 0; } dijkstra(field, cost, ox, oy); if(oasis_life*2 - cost[len-1][len-1] > 0) { printf("YES"); return 0; } } printf("NO"); return 0; }