#include using namespace std; struct Edge { typedef int CostType; const static int cost = 1; int from, to; Edge(int from, int to) : from(from), to(to) {}; }; template struct WeightedEdge : public Edge { typedef Cost CostType; Cost cost; WeightedEdge(int from, int to, Cost cost = 0) : Edge(from, to), cost(cost) {} }; template struct ResidualEdge : public Edge { typedef Capacity CapacityType; Capacity cap; int rev; ResidualEdge(int from, int to, Capacity cap) : Edge(from, to), cap(cap) {} ResidualEdge reverse() const {return ResidualEdge(to, from, 0);} }; template struct WeightedResidualEdge : public ResidualEdge { Cost cost; WeightedResidualEdge(int from, int to, Capacity cap, Cost cost) : ResidualEdge(from, to, cap), cost(cost) {} WeightedResidualEdge reverse() const {return WeightedResidualEdge(this->to, this->from, 0, -cost);} }; template class Graph { public: typedef Edge EdgeType; virtual int size() const = 0; template void addEdge(Args...) {} template void addUndirectedEdge(Args...) {} virtual vector getEdges() const = 0; virtual vector getEdges(int from) const = 0; virtual vector getEdges(int from, int to) const = 0; virtual int getDegree(int v) const = 0; }; template class AdjacencyList : public Graph { protected: vector> graph; public: AdjacencyList(int n) : graph(n) {} int size() const { return graph.size(); } template void addEdge(Args... args) { Edge edge(args...); graph[edge.from].emplace_back(edge); } template void addUndirectedEdge(Args... args) { Edge edge(args...); addEdge(edge); swap(edge.from, edge.to); addEdge(edge); } vector getEdges() const { vector res; for (const auto& edges : graph) { res.insert(res.end(), edges.begin(), edges.end()); } return res; } vector getEdges(int from) const { return graph[from]; } vector getEdges(int from, int to) const { vector res; for (const auto& edge : graph[from]) { if (edge.to == to) res.emplace_back(edge); } return res; } int getDegree(int v) const { return graph[v].size(); } vector& operator[](int v) { return graph[v]; } }; template class Search { protected: typedef typename Graph::EdgeType Edge; const Graph graph; vector visited; virtual void push(const State&) = 0; virtual State next() = 0; virtual bool isRunning() = 0; virtual void visit(const State&) {} virtual bool canPruning(const State&) {return false;} public: Search(const Graph& graph) : graph(graph), visited(graph.size(), false) {} void solve(int from) { push(State(from)); while (isRunning()) { State now = next(); int pos = now.getPos(); if (visited[pos]) continue; visited[pos] = true; visit(now); for (const Edge& edge : graph.getEdges(pos)) { State nextState = now.next(edge); if (visited[nextState.getPos()]) continue; if (canPruning(nextState)) continue; push(nextState); } } } bool isReachable(int v) { return visited[v]; } }; template class Tree { public: vector parent; vector> children; vector depth; Tree() {} Tree(int n) : children(n), depth(n, -1) { for (int i = 0; i < n; ++i) parent.emplace_back(i, i); } int size() const { return parent.size(); } template void addEdge(Args... args) { Edge edge(args...); parent[edge.from] = edge; if (edge.from != edge.to) children[edge.to].emplace_back(edge.from); } int getDepth(int v) { if (depth[v] != -1) return depth[v]; if (parent[v].to == v) return depth[v] = 0; return depth[v] = getDepth(parent[v].to) + 1; } vector getPath(int v) { vector res{v}; while (v != parent[v].to) { v = parent[v].to; res.emplace_back(v); } return res; } }; template struct DijkstraState { typedef typename Edge::CostType Cost; Edge edge; Cost cost; DijkstraState(int pos) : edge(pos, pos), cost(0) {} DijkstraState(const Edge& edge, Cost cost) : edge(edge), cost(cost) {} DijkstraState next(const Edge& edge) const { return DijkstraState(edge, cost + edge.cost); } bool operator<(const DijkstraState& state) const { return cost > state.cost; } int getPos() const { return edge.to; } }; template> class Dijkstra : public Search { protected: typedef typename Graph::EdgeType Edge; typedef typename Edge::CostType Cost; const Cost INF = numeric_limits::max(); priority_queue que; void push(const State& state) { que.push(state); dis[state.getPos()] = state.cost; } State next() { State now = que.top(); que.pop(); return now; } bool isRunning() { return !que.empty(); } void visit(const State& state) { if (Restoration) { auto e = state.edge; swap(e.from, e.to); shortestPathTree.addEdge(e); } } bool canPruning(const State& state) { return dis[state.getPos()] <= state.cost; } public: vector dis; Tree shortestPathTree; Dijkstra(const Graph& graph) : Search(graph), dis(graph.size(), INF) { if (Restoration) shortestPathTree = Tree(graph.size()); } }; template inline Dijkstra shortestPath(Graph& graph, int from) { Dijkstra dijkstra(graph); dijkstra.solve(from); return dijkstra; } template inline typename Graph::EdgeType::CostType shortestPath(Graph& graph, int from, int to) { Dijkstra dijkstra(graph); dijkstra.solve(from); return dijkstra.dis[to]; } template inline Dijkstra shortestPathTree(Graph& graph, int from) { Dijkstra dijkstra(graph); dijkstra.solve(from); return dijkstra; } int main() { int n, v, x, y; cin >> n >> v >> x >> y; --x, --y; vector> l(n, vector(n)); for (auto& i : l) { for (int& j : i) cin >> j; } AdjacencyList> graph(n * n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != n - 1) { graph.addEdge(i * n + j, i * n + j + n, l[i + 1][j]); graph.addEdge(i * n + j + n, i * n + j, l[i][j]); } if (j != n - 1) { graph.addEdge(i * n + j, i * n + j + 1, l[i][j + 1]); graph.addEdge(i * n + j + 1, i * n + j, l[i][j]); } } } if (shortestPath(graph, 0, n * n - 1) < v) { cout << "YES" << endl; return 0; } if (x == -1 && y == -1) { cout << "NO" << endl; return 0; } int d1 = shortestPath(graph, 0, y * n + x); int d2 = shortestPath(graph, y * n + x, n * n - 1); cout << ((v - d1) * 2 > d2 ? "YES" : "NO") << endl; }