#include #include #include #include #include #include using namespace std; struct Item { int x; int y; int cost; bool operator<(const Item& rhs) const { return cost < rhs.cost; } }; int DIR_X[] = {-1, 1, 0, 0}; int DIR_Y[] = { 0, 0, 1, -1}; typedef vector > cost_matrix_t; cost_matrix_t dijkstra(int field[][200], int sx, int sy, int len_x, int len_y) { auto queue = priority_queue(); auto costmatrix = vector>(len_x, vector(len_y, INT_MAX)); queue.push(Item{sx,sy,0}); costmatrix[sx][sy] = 0; while(!queue.empty()) { Item item = queue.top(); queue.pop(); if(item.cost <= costmatrix[item.x][item.y]) { for(int i=0; i<4; i++) { int nx = item.x + DIR_X[i]; if(nx<0 || len_x<=nx) continue; int ny = item.y + DIR_Y[i]; if(ny<0 || len_y<=ny) continue; int c = item.cost + field[nx][ny]; if(c0 || oy>0) { cost_matrix_t c2 = dijkstra(field, ox, oy, len, len); if((life - c[ox][oy])*2 - c2[len-1][len-1] > 0) { printf("YES"); } else { printf("NO"); } } else { printf("NO"); } return 0; }