using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ProgrammingContest { class MainClass : IDisposable { Scanner sc; Writer wr; string backPath = ".."; char dirSep = System.IO.Path.DirectorySeparatorChar; string inFilePath = null; string outFilePath = null; public MainClass() { this.inFilePath = this.backPath + this.dirSep + this.backPath + this.dirSep + "in.txt"; this.outFilePath = this.backPath + this.dirSep + this.backPath + this.dirSep + "out.txt"; } static void Main(string[] args) { using (var mainClass = new MainClass()) { //mainClass.MakeTestCase(); mainClass.Solve(); } } public void Dispose() { if (this.sc != null) { this.sc.Dispose(); this.sc = null; } if (this.wr != null) { this.wr.Dispose(); this.wr = null; } } void MakeTestCase() { Random rand = new Random(); var res = new StringBuilder(); using (var writer = new System.IO.StreamWriter(inFilePath)) writer.Write(res.ToString()); } void Solve() { this.wr = new Writer(this.isReactive); //this.wr = new Writer(this.outFilePath); #if DEBUG if (!this.isReactive) this.sc = new Scanner(this.inFilePath); else this.sc = new Scanner(); #else this.sc = new Scanner(); #endif N = sc.NextInt; V = sc.NextInt; oasis = new Point { y = sc.NextInt - 1, x = sc.NextInt - 1 }; L = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { L[i, j] = sc.NextInt; } } var st = new Point() { x = 0, y = 0 }; var ed = new Point() { x = N - 1, y = N - 1 }; string ans = "NO"; if (Dijkstra(st, ed) < V) { ans = "YES"; } else if (!oasis.Equals(new Point() { x = -1, y = -1 })) { int f = Dijkstra(st, oasis); if (f < V) { int ff = Dijkstra(oasis, ed); //wr.WriteLine("{0} {1} {2}", f, ff, V); if (ff < (V - f) * 2) { ans = "YES"; } } } wr.WriteLine(ans); } int Dijkstra(Point st, Point ed) { var heap = new SkewHeap(); heap.Push(new State(st)); int[,] u = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { u[i, j] = (int)1e9; } } u[st.y, st.x] = 0; int preCost = 0; while (!heap.IsEmpty()) { var state = heap.Poll(); if (preCost > state.Cost) throw new Exception(); preCost = state.Cost; if (state.p.Equals(ed)) { return state.Cost; } var nextPoint = state.p.Next(); foreach (var p in nextPoint) { if (Inside(p)) { int nextCost = state.Cost + L[p.y, p.x]; if (nextCost < u[p.y, p.x]) { u[p.y, p.x] = nextCost; heap.Push(new State(p, nextCost)); } } } } return -1; } int N, V; Point oasis; int[,] L; bool Inside(Point p) { return 0 <= p.x && p.x < N && 0 <= p.y && p.y < N; } struct State : IComparable { public Point p; public int Cost; public State(int nx, int ny) { p = new Point { x = nx, y = ny }; Cost = 0; } public State(Point p, int cost = 0) { this.p = p; this.Cost = cost; } public int CompareTo(State other) { return Math.Sign(this.Cost - other.Cost); } } struct Point { public int x, y; static Point[] dPoint = new Point[] { new Point{ x = 0, y = -1}, new Point{ x = -1, y = 0}, new Point{ x = 0, y = 1}, new Point{ x = 1, y = 0}, }; private Point Next(Point d) { return new Point { x = this.x + d.x, y = this.y + d.y }; } public List Next() { List ret = new List(); foreach (var el in dPoint) { ret.Add(this.Next(el)); } return ret; } public override bool Equals(object other) { return (other is Point) && ((Point)other).x == this.x && ((Point)other).y == this.y; } } bool isReactive = false; // TODO: reactive check !! } class SkewHeap where T : IComparable { private class HeapNode { public HeapNode l, r; public T val; public static Func CompareTo; public HeapNode(T val) { this.val = val; l = r = null; } public static HeapNode Meld(HeapNode leftNode, HeapNode rightNode) { if (leftNode == null) { return rightNode; } if (rightNode == null) { return leftNode; } if (HeapNode.CompareTo(leftNode.val, rightNode.val) > 0) { var t = rightNode; rightNode = leftNode; leftNode = t; } leftNode.r = Meld(leftNode.r, rightNode); var t2 = leftNode.l; leftNode.l = leftNode.r; leftNode.r = t2; return leftNode; } } private HeapNode topNode; private int count_; public int Count { get { return this.count_; } } public SkewHeap(Func comp = null) { HeapNode.CompareTo = (comp ?? ((T l, T r) => l.CompareTo(r))); this.topNode = null; this.count_ = 0; } public void Pop() { this.topNode = HeapNode.Meld(this.topNode.l, this.topNode.r); this.count_--; } public T Top() { return this.topNode.val; } public void Push(T val) { this.topNode = HeapNode.Meld(this.topNode, new HeapNode(val)); this.count_++; } public T Poll() { T retVal = this.Top(); this.Pop(); return retVal; } public bool IsEmpty() { return this.topNode == null; } public void Merge(SkewHeap otherHeap) { this.count_ += otherHeap.Count; this.topNode = HeapNode.Meld(this.topNode, otherHeap.topNode); } } class Writer : IDisposable { System.IO.TextWriter writer; StringBuilder sb; bool isReactive; public Writer(string path) : this(new System.IO.StreamWriter(path)) { } public Writer(bool isReactive) : this(null, isReactive) { } public Writer(System.IO.TextWriter writer = null, bool isReactive = false) { this.writer = (writer ?? Console.Out); if (!(this.isReactive = isReactive)) { this.sb = new StringBuilder(); } } public void Dispose() { if (!isReactive) this.writer.Write(sb.ToString()); if (!this.writer.Equals(Console.Out)) this.writer.Dispose(); } public void Write(object val) { if (this.isReactive) { this.writer.Write(val.ToString()); this.writer.Flush(); } else this.sb.Append(val.ToString()); } public void Write(string format, params object[] vals) { if (this.isReactive) { this.writer.Write(format, vals); this.writer.Flush(); } else this.sb.AppendFormat(format, vals); } public void WriteLine(object val) { this.Write(val.ToString() + System.Environment.NewLine); } public void WriteLine(string format, params object[] vals) { this.Write(format + System.Environment.NewLine, vals); } } class Scanner : IDisposable { Queue buffer; char[] sep; System.IO.TextReader reader; public Scanner(string path) : this(new System.IO.StreamReader(path)) { } public Scanner(System.IO.TextReader reader = null) { this.buffer = new Queue(); this.sep = new char[] { ' ' }; this.reader = (reader ?? Console.In); } private void CheckBuffer() { if (this.buffer.Count == 0) { string str = null; while (string.IsNullOrEmpty(str)) { str = this.reader.ReadLine(); } string[] sreArray = str.Split(this.sep); foreach (string elStr in sreArray) { this.buffer.Enqueue(elStr); } } } public void Dispose() { if (!this.reader.Equals(Console.In)) this.reader.Dispose(); } public string Next { get { this.CheckBuffer(); return this.buffer.Dequeue(); } } public int NextInt { get { return int.Parse(this.Next); } } public double NextDouble { get { return double.Parse(this.Next); } } public long NextLong { get { return long.Parse(this.Next); } } public bool IsEmpty { get { this.CheckBuffer(); return this.buffer.Count == 0; } } } }