#include #include #include #include #include using namespace std; int n; int index(int x, int y) { return x + y * (n + 1); } struct Node { Node(int distance, int node) : distance(distance), node(node) {} int distance; int node; }; bool operator<(const Node& lhs, const Node& rhs) { return lhs.distance > rhs.distance; } int shortest(const map >& costs, int nodeCount, int startNode, int endNode) { vector distance(nodeCount, numeric_limits::max()); distance[startNode] = 0; priority_queue shortests; shortests.push(Node(distance[startNode], startNode)); vector determined(nodeCount, false); while (!shortests.empty()) { Node edge = shortests.top(); shortests.pop(); determined[edge.node] = true; int shortestNode = edge.node; map >::const_iterator itCosts = costs.find(shortestNode); if (itCosts == costs.end()) { continue; } for (map::const_iterator it = itCosts->second.begin(); it != itCosts->second.end(); ++it) { int adjNode = it->first; if (determined[adjNode]) { continue; } int cost = it->second; int newDistance = distance[shortestNode] + cost; if (newDistance < distance[adjNode]) { distance[adjNode] = newDistance; shortests.push(Node(newDistance, adjNode)); } } } return distance[endNode]; } int main() { int v, ox, oy; cin >> n >> v >> ox >> oy; vector > l(n, vector(n)); for (int y = 0; y < n; ++y) { for (int x = 0; x < n; ++x) { cin >> l[x][y]; } } int nodeCount = (n + 1) * n; map > costs; for (int y = 0; y < n; ++y) { for (int x = 0; x < n; ++x) { if (x < n - 1) { costs[index(x, y)][index(x + 1, y)] = l[x][y]; costs[index(x + 1, y)][index(x, y)] = l[x][y]; } if (x > 0) { costs[index(x, y)][index(x - 1, y)] += l[x][y]; costs[index(x - 1, y)][index(x, y)] += l[x][y]; } if (y < n - 1) { costs[index(x, y)][index(x, y + 1)] = l[x][y]; costs[index(x, y + 1)][index(x, y)] = l[x][y]; } if (y > 0) { costs[index(x, y)][index(x, y - 1)] += l[x][y]; costs[index(x, y - 1)][index(x, y)] += l[x][y]; } } } int startNode = index(n, 0); costs[startNode][index(0, 0)] = l[0][0]; int endNode = index(n, 1); costs[index(n - 1, n - 1)][endNode] = l[n - 1][n - 1]; int minCost = shortest(costs, nodeCount, startNode, endNode); bool possible = false; if (minCost < v * 2) { possible = true; } if (!possible && ox != 0 && oy != 0) { costs[index(n - 1, n - 1)].erase(endNode); costs[index(ox, oy)][endNode] = l[ox][oy]; int toOasisCost = shortest(costs, nodeCount, startNode, endNode); if (toOasisCost < v * 2) { int regainedEnergy = (v * 2 - toOasisCost) * 2; costs[startNode].erase(index(0, 0)); if (ox < n - 1) { costs[startNode][index(ox + 1, oy)] = l[ox + 1][oy]; } if (ox > 0) { costs[startNode][index(ox - 1, oy)] = l[ox - 1][oy]; } if (oy < n - 1) { costs[startNode][index(ox, oy + 1)] = l[ox][oy + 1]; } if (oy > 0) { costs[startNode][index(ox, oy - 1)] = l[ox][oy - 1]; } costs[index(ox, oy)].erase(endNode); costs[index(n - 1, n - 1)][endNode] = l[n - 1][n - 1]; int fromOasisCost = shortest(costs, nodeCount, startNode, endNode); if (fromOasisCost < regainedEnergy) { possible = true; } } } cout << (possible ? "YES" : "NO") << endl; return 0; }