#line 2 "header.hpp" //%snippet.set('header')% //%snippet.fold()% #ifndef HEADER_H #define HEADER_H // template version 2.0 using namespace std; #include // varibable settings const long long INF = 1e18; template constexpr T inf = numeric_limits::max() / 2.1; #define _overload3(_1, _2, _3, name, ...) name #define _rep(i, n) repi(i, 0, n) #define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i) #define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__) #define _rrep(i, n) rrepi(i, 0, n) #define rrepi(i, a, b) for (ll i = (ll)((b)-1); i >= (ll)(a); --i) #define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__) #define each(i, a) for (auto &&i : a) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define pb(a) push_back(a) #define mp(a, b) make_pair(a, b) #define mt(...) make_tuple(__VA_ARGS__) #define ub upper_bound #define lb lower_bound #define lpos(A, x) (lower_bound(all(A), x) - A.begin()) #define upos(A, x) (upper_bound(all(A), x) - A.begin()) template inline void chmax(T &a, const T &b) { if ((a) < (b)) (a) = (b); } template inline void chmin(T &a, const T &b) { if ((a) > (b)) (a) = (b); } template auto make_table(X x, T a) { return vector(x, a); } template auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector(x, cont); } #define divceil(a, b) ((a) + (b)-1) / (b) #define is_in(x, a, b) ((a) <= (x) && (x) < (b)) #define uni(x) sort(all(x)); x.erase(unique(all(x)), x.end()) #define slice(l, r) substr(l, r - l) typedef long long ll; typedef long double ld; using vl = vector; using vvl = vector; using pll = pair; template using PQ = priority_queue, greater>; void check_input() { assert(cin.eof() == 0); int tmp; cin >> tmp; assert(cin.eof() == 1); } #if defined(PCM) || defined(LOCAL) #else #define dump(...) ; #define dump_1d(...) ; #define dump_2d(...) ; #define cerrendl ; #endif #endif /* HEADER_H */ //%snippet.end()% #line 2 "solve.cpp" template using vec = vector; struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast; // snippet:segment_tree {{{ template struct SegmentTree { // {{{ private: using F = function; int n; // 元の配列のサイズ int N; // n以上の最小の2冪 vector node; F merge; T identity; public: SegmentTree() {} SegmentTree(vector a, F f, T id) : merge(f), identity(id) { n = a.size(); N = 1; while (N < n) N *= 2; node.resize(2 * N - 1, identity); for (int i = 0; i < n; i++) node[i + N - 1] = a[i]; for (int i = N - 2; i >= 0; i--) node[i] = merge(node[2 * i + 1], node[2 * i + 2]); } SegmentTree(int n, F f, T id) : SegmentTree(vector(n, id), f, id) {} T& operator[](int i) { return node[i + N - 1]; } void update(int i, T val) { i += (N - 1); node[i] = val; while (i > 0) { i = (i - 1) / 2; node[i] = merge(node[2 * i + 1], node[2 * i + 2]); } } void add(int i, T val) { i += (N - 1); node[i] += val; while (i > 0) { i = (i - 1) / 2; node[i] = merge(node[2 * i + 1], node[2 * i + 2]); } } // query for [l, r) T query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (r <= a || b <= l) return identity; if (a <= l && r <= b) return node[k]; T vl = query(a, b, 2 * k + 1, l, (l + r) / 2); T vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return merge(vl, vr); } #if defined(PCM) || defined(LOCAL) friend ostream& operator<<(ostream& os, SegmentTree& sg) { // os << "["; for (int i = 0; i < sg.n; i++) { os << sg[i] << (i == sg.n - 1 ? "]\n" : ", "); } return os; } #endif };/*}}}*/ // sample of initialize SegmentTree: // ----------------------------------------------- // auto mymin=[](auto a, auto b){return min(a,b);}; // SegmentTree seg(a, mymin, 1e18); // auto mymax=[](auto a, auto b){return max(a,b);}; // SegmentTree seg(a, mymax, -1e18); // auto add=[](auto a, auto b){return a+b;}; // SegmentTree seg(a, add, 0); // ----------------------------------------------- // snippet:segment_tree }}} // snippet:edge {{{ template struct Edge { int from, to; Cost cost; int idx; Edge(){}; Edge(int from, int to, Cost cost, int idx) : from(from), to(to), cost(cost), idx(idx) {} friend ostream& operator<<(ostream& os, const Edge& e) { // os << "(f:" << e.from << ", t:" << e.to << ", c:" << e.cost << ", i" << e.idx << ")"; // detailed os << "(" << e.from << "," << e.to << ")"; return os; } }; // snippet:edge }}} // snippet:UnionFind {{{ struct UnionFind { vector par; // par[x]: parent of x. if root, -size. int gcount; // count of groups UnionFind() {} UnionFind(int _n) : par(_n, -1), gcount(_n) {} bool merge(int x, int y) { x = root(x); y = root(y); if (x != y) { if (par[y] < par[x]) swap(x, y); par[x] += par[y]; par[y] = x; gcount--; } return x != y; } int root(int x) { if (is_root(x)){ return x; } else{ return par[x] = root(par[x]); // 経路圧縮 // return root(par[x]); // 経路圧縮なし } } bool is_root(int x) { return par[x] < 0; } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -par[root(x)]; } #if defined(PCM) || defined(LOCAL) // {{{ friend ostream& operator<<(ostream& os, UnionFind& uf) { map> group; rep(i, sz(uf.par)) { group[uf.root(i)].pb(i); } os << endl; each(g, group) { os << g << endl; } return os; } #endif // }}} }; // snippet:UnionFind }}} // snippet:tree {{{ template struct tree { int n; vector par; // par[i]: dfs木における親 vector cost; // par[i]: dfs木における親への辺のコスト vector dfstrv; // dfstrv[i]: dfs木でi番目に訪れるノード。dpはこれを逆順に回す vector ord; // ord[u]: uのdfs木における訪問順 vector end; // end[u]: uのdfs終了時のカウンター vector psize; // psize[u]: uのpartial tree size // uの部分木は[ord[u], end[u]) // ordとdfstrvは逆変換 vector depth; // depth[i]: dfs木でのiの深さ vector ldepth; // ldepth[i]: dfs木でのrootからの距離 vector>> adj_list; // 辺(隣接リスト) auto operator[](int pos) const { return adj_list[pos]; } vector> children; vector euler_tour; vector et_fpos; // euler_tour first occurence position SegmentTree _seg; // seg(map(ord, euler_tour), mymin, 1e18) vector head_of_comp; int _counter = 0; tree(){};/*{{{*/ tree(int n) : n(n), par(n), cost(n), ord(n), end(n), psize(n), depth(n), ldepth(n), adj_list(n), children(n), et_fpos(n), head_of_comp(n){};/*}}}*/ void add_edge(int u, int v, Cost cost, int idx=-1) { /*{{{*/ adj_list[u].emplace_back(u, v, cost, idx); adj_list[v].emplace_back(v, u, cost, idx); } /*}}}*/ void add_edge(int u, int v) { /*{{{*/ adj_list[u].emplace_back(u, v, 1, -1); adj_list[v].emplace_back(v, u, 1, -1); } /*}}}*/ void build(int root) { /*{{{*/ _counter = 0; // par[root] = -1; // cost[root] = -1; _dfs_psize(root, -1); _dfs_tree(root, -1, root); _dfs_et(root); vector ini(2 * n - 1); rep(i, 2 * n - 1) ini[i] = ord[euler_tour[i]]; _seg = SegmentTree( ini, [](auto a, auto b) { return min(a, b); }, numeric_limits().max()); } /*}}}*/ int _dfs_psize(int u, int pre) { /*{{{*/ psize[u] = 1; each(edge, adj_list[u]) { if (edge.to == pre) continue; psize[u] += _dfs_psize(edge.to, u); } return psize[u]; } /*}}}*/ void _dfs_tree(int u, int pre, int head_node) { /*{{{*/ dfstrv.pb(u); ord[u] = _counter; if (pre != -1) { depth[u] = depth[pre] + 1; ldepth[u] = ldepth[pre] + cost[u]; } _counter++; { // set most heavy child to top int max_psize = 0; int most_heavy_i = -1; rep(i, sz(adj_list[u])) { if (adj_list[u][i].to == pre) continue; if (psize[adj_list[u][i].to] > max_psize) { most_heavy_i = i; max_psize = psize[adj_list[u][i].to]; } } if (most_heavy_i != -1) swap(adj_list[u][most_heavy_i], adj_list[u][0]); } head_of_comp[u] = head_node; rep(i, sz(adj_list[u])) { int v = adj_list[u][i].to; if (v == pre) continue; children[u].pb(v); par[v] = u; cost[v] = adj_list[u][i].cost; if (i == 0) _dfs_tree(v, u, head_node); // continue components else _dfs_tree(v, u, v); // new } end[u] = _counter; } /*}}}*/ void _dfs_et(int u) { /*{{{*/ et_fpos[u] = euler_tour.size(); euler_tour.pb(u); each(v, children[u]) { _dfs_et(v); euler_tour.pb(u); } } /*}}}*/ int lca(int u, int v) { /*{{{*/ if (u == v) return u; if (et_fpos[u] > et_fpos[v]) swap(u, v); return dfstrv[_seg.query(et_fpos[u], et_fpos[v])]; } /*}}}*/ int dist(int u, int v) { /*{{{*/ int p = lca(u, v); return depth[u] + depth[v] - 2 * depth[p]; } /*}}}*/ Cost ldist(int u, int v) { // length dist{{{ int p = lca(u, v); return ldepth[u] + ldepth[v] - 2 * ldepth[p]; } /*}}}*/ pair diameter() { /*{{{*/ int u, v; Cost max_len = *max_element(all(ldepth)); rep(i, n) { if (ldepth[i] == max_len) { u = i; break; } } Cost md = -1; rep(i, n) { Cost d = ldist(u, i); if (d > md) { v = i; md = d; } } return mp(u, v); } /*}}}*/ vector> hld_path(int u, int v, bool for_edge=true) { //{{{ // 閉区間をvectorで返す。for_edge=trueでlcaは除いて返すことに注意。 vector> res; while (head_of_comp[u] != head_of_comp[v]) { if (depth[head_of_comp[u]] < depth[head_of_comp[v]]) { res.push_back({ord[head_of_comp[v]], ord[v]}); v = par[head_of_comp[v]]; } else { res.push_back({ord[head_of_comp[u]], ord[u]}); u = par[head_of_comp[u]]; } } res.push_back({min(ord[u], ord[v]) + (for_edge?1:0), max(ord[u], ord[v])}); return res; } //}}} #if defined(PCM) || defined(LOCAL) /*{{{*/ friend ostream& operator<<(ostream& os, const tree& tr) { os << endl; os << "par: " << tr.par << endl; os << "cost: " << tr.cost << endl; os << "dfstrv: " << tr.dfstrv << endl; os << "ord: " << tr.ord << endl; os << "end: " << tr.end << endl; os << "depth: " << tr.depth << endl; os << "children: " << tr.children << endl; os << "euler_tour: " << tr.euler_tour << endl; os << "et_fpos: " << tr.et_fpos << endl; os << "head_of_comp:" << tr.head_of_comp << endl; return os; } #endif /*}}}*/ }; // snippet:tree }}} // snippet:Graph {{{ template struct Graph { using Pos = int; // int以外には対応しない。 int n; // 頂点数 vector>> adj_list; auto operator[](Pos pos) const { return adj_list[pos]; } vector> edges; tree tr; Pos root; vector _used_in_dfs; vector lowlink; Cost zerocost; Cost infcost; Graph() {} Graph(int _n) : n(_n), adj_list(_n), tr(n), _used_in_dfs(n), zerocost(0LL), infcost(INF) { } Graph(int _n, Cost zc, Cost ic) : n(_n), adj_list(_n), tr(n), _used_in_dfs(n), zerocost(zc), infcost(ic) { } void add_edge(Pos from, Pos to, Cost cost, int idx=-1) {/*{{{*/ adj_list[from].emplace_back(from, to, cost, idx); edges.emplace_back(from, to, cost, idx); } void add_edge(Pos from, Pos to) { // for ll adj_list[from].emplace_back(from, to, 1, -1); edges.emplace_back(from, to, 1, -1); }/*}}}*/ void build_tree(Pos _root) {/*{{{*/ root = _root; _dfs_tree(root); tr.build(root); _make_lowlink(); }/*}}}*/ vector make_bipartite() {/*{{{*/ UnionFind buf(2 * n); rep(u, n) { each(e, adj_list[u]) { buf.merge(u, e.to + n); buf.merge(e.to, u + n); } } vector res(n, -1); rep(u, n) { if (buf.same(u, u + n)) return res; } rep(u, n) { if (buf.same(0, u)) res[u] = 0; else res[u] = 1; } return res; }/*}}}*/ void _dfs_tree(Pos u) {/*{{{*/ _used_in_dfs[u] = 1; each(e, adj_list[u]) { if (_used_in_dfs[e.to]) continue; tr.add_edge(u, e.to, e.cost); _dfs_tree(e.to); } }/*}}}*/ void _make_lowlink() {/*{{{*/ lowlink = vector(n, numeric_limits().max()); r_rep(i, n) { Pos u = tr.dfstrv[i]; chmin(lowlink[u], tr.ord[u]); each(e, adj_list[u]) { if (e.to == tr.par[u]) continue; else if (tr.ord[e.to] < tr.ord[u]) { chmin(lowlink[u], tr.ord[e.to]); } else { chmin(lowlink[u], lowlink[e.to]); } } } }/*}}}*/ vector get_articulation_points() {/*{{{*/ if (sz(lowlink) == 0) throw("make_lowlik() beforehand"); vector res; if (sz(tr.children[root]) > 1) { res.push_back(root); } rep(u, 0, n) { if (u == root) continue; bool is_kan = false; each(v, tr.children[u]) { if (tr.ord[u] <= lowlink[v]) { is_kan = true; } } if (is_kan) res.push_back(u); } return res; }/*}}}*/ vector> get_bridges() {/*{{{*/ if (sz(lowlink) == 0) throw("make_lowlik() beforehand"); vector> res; each(edge, edges){ if (tr.ord[edge.from] < lowlink[edge.to]) res.push_back(edge); } return res; }/*}}}*/ vector> kruskal_tree() {/*{{{*/ // 使用される辺のvectorを返す vector> res(n - 1); sort(all(edges), [&](auto l, auto r) { return l.cost < r.cost; }); UnionFind uf(n); Cost total_cost = zerocost; int idx = 0; each(e, edges) { if (uf.same(e.from, e.to)) continue; uf.merge(e.from, e.to); total_cost = total_cost + e.cost; res[idx] = e; idx++; } assert(idx == n - 1); return res; }/*}}}*/ vector dijkstra(vector starts) { // 多点スタート{{{ vector dist(n, infcost); // 最短距離 PQ> pq; each(start, starts) { dist[start] = zerocost; pq.push(make_pair(zerocost, start)); } while (!pq.empty()) { auto cp = pq.top(); pq.pop(); auto [cost, u] = cp; for (const auto& edge : adj_list[u]) { Cost new_cost = cost + edge.cost; // TODO: 問題によってはここが変更の必要あり if (new_cost < dist[edge.to]) { dist[edge.to] = new_cost; pq.push(make_pair(new_cost, edge.to)); } } } return dist; };/*}}}*/ vector dijkstra(Pos start) { // 1点スタート{{{ vector starts = {start}; return dijkstra(starts); };/*}}}*/ }; // snippet:Graph }}} int solve() { ll m,v,ox,oy;cin>>m>>v>>ox>>oy; ox--;oy--; // grid graphを通常のグラフに格納する。 int h, w; h = m; w = m; int n = h * w; // 頂点数 vvl block = make_table(m, m, 0LL); rep(i, h)rep(j, w) cin>>block[i][j]; Graph g(n); auto nid = [&](int i, int j){return (i*w + j);}; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; rep(i, h) rep(j, w) { rep(dir, 4) { int ni = i + dx[dir]; int nj = j + dy[dir]; if (is_in(ni, 0, h) && is_in(nj, 0, w)) { g.add_edge(nid(i, j), nid(ni, nj), block[ni][nj]); } } } auto d = g.dijkstra(nid(0, 0)); auto rd = g.dijkstra(nid(m-1, m-1)); if (ox==-1 && oy==-1){ if (d[nid(m-1, m-1)]<=v-1){ cout << "YES" << endl; return 0; } else{ cout << "NO" << endl; return 0; } } else{ if (d[nid(m-1, m-1)]<=v-1){ cout << "YES" << endl; return 0; } if (ll rem = v - d[nid(ox, oy)]; rem > 0){ ll vv = rem*2; if (rd[nid(ox, oy)] < vv){ cout << "YES" << endl; return 0; } else{ cout << "NO" << endl; return 0; } } else{ cout << "NO" << endl; } } return 0; } int main(){/*{{{*/ solve(); check_input(); return 0; }/*}}}*/