#include #include #include #include const int di[] = {0, 0, 1, -1}; const int dj[] = {1, -1, 0, 0}; std::vector> dijkstra(const std::vector> &grid, int si, int sj) { using P = std::tuple; int h = grid.size(); int w = grid[0].size(); std::vector> distance(h, std::vector(w, 1LL << 60)); distance[si][sj] = 0LL; std::priority_queue, std::greater

> pq; pq.emplace(0LL, si, sj); while (not pq.empty()) { auto p = pq.top(); pq.pop(); int& i = std::get<1>(p); int& j = std::get<2>(p); if (distance[i][j] < std::get<0>(p)) continue; for (int k = 0; k < 4; k++) { int nxt_i = i + di[k]; int nxt_j = j + dj[k]; if (nxt_i < 0 || h <= nxt_i) continue; if (nxt_j < 0 || w <= nxt_j) continue; if (distance[nxt_i][nxt_j] > distance[i][j] + grid[nxt_i][nxt_j]) { distance[nxt_i][nxt_j] = distance[i][j] + grid[nxt_i][nxt_j]; pq.emplace(distance[nxt_i][nxt_j], nxt_i, nxt_j); } } } return distance; } int main() { long long v; int n, oj, oi; std::cin >> n >> v >> oj >> oi; oj -= 1; oi -= 1; std::vector> l(n, std::vector(n, 0)); for (auto& inner : l) { for (auto& val : inner) { std::cin >> val; } } auto distance = dijkstra(l, 0, 0); if (v - distance[n - 1][n - 1] > 0) { std::cout << "YES" << std::endl; return 1; } if (oi == -1 && oj == -1) { std::cout << "NO" << std::endl; return 1; } if (v - distance[oi][oj] <= 0) { std::cout << "NO" << std::endl; return 1; } v -= distance[oi][oj]; v *= 2; auto mid_distance = dijkstra(l, oi, oj); if (v - distance[n - 1][n - 1] > 0) { std::cout << "YES" << std::endl; } else { std::cout << "NO" << std::endl; } }