using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Text; using System.Text.RegularExpressions; using System.Linq; using System.IO; class Program { static void Main(string[] args) { new Magatro().Solve(); } } public class Scanner { private StreamReader Sr; private string[] S; private int Index; private const char Separator = ' '; public Scanner(Stream source) { Index = 0; S = new string[0]; Sr = new StreamReader(source); } public Scanner() : this(Console.OpenStandardInput()) { } private string[] Line() { return Sr.ReadLine().Split(Separator); } public string Next() { string result; if (Index >= S.Length) { S = Line(); Index = 0; } result = S[Index]; Index++; return result; } public int NextInt() { return int.Parse(Next()); } public double NextDouble() { return double.Parse(Next()); } public long NextLong() { return long.Parse(Next()); } public decimal NextDecimal() { return decimal.Parse(Next()); } public string[] StringArray(int index = 0) { Next(); Index = S.Length; return S.Skip(index).ToArray(); } public int[] IntArray(int index = 0) { return StringArray(index).Select(int.Parse).ToArray(); } public long[] LongArray(int index = 0) { return StringArray(index).Select(long.Parse).ToArray(); } public bool EndOfStream { get { return Sr.EndOfStream; } } } public class PriortyQueue { private Comparison Comparator; private List L; public PriortyQueue(Comparison comparator) { Clear(); Comparator = comparator; } public PriortyQueue(PriortyQueue queue) { L = queue.ToList(); Comparator = queue.Comparator; } public void Add(T item) { int n = L.Count; L.Add(item); while (n > 0) { int i = (n - 1) / 2; if (Comparator(L[n], L[i]) > 0) { Swap(n, i); } n = i; } } public T Poll() { T ret = Peak(); Pop(); return ret; } public void Pop() { int n = L.Count - 1; L[0] = L[n]; L.RemoveAt(n); for (int i = 0, j; (j = 2 * i + 1) < n;) { if ((j != n - 1) && (Comparator(L[j], L[j + 1]) < 0)) { j++; } if (Comparator(L[i], L[j]) < 0) { Swap(i, j); } i = j; } } public T Peak() { return L[0]; } public T[] ToArray() { return L.ToArray(); } public List ToList() { return L.ToList(); } public void Clear() { L = new List(); } public int Size { get { return L.Count; } } public bool IsEmpty { get { return L.Count == 0; } } private void Swap(int a, int b) { T temp = L[a]; L[a] = L[b]; L[b] = temp; } public int Count { get { return L.Count; } } } struct Cell { public int X, Y, Life; public Cell(int x, int y, int life) { X = x; Y = y; Life = life; } } class Magatro { private int N, V, Ox, Oy; private int[][] L; private bool[,] B; private int[] Next = new int[] { 1, 0, -1, 0 }; public void Solve() { var cin = new Scanner(); N = cin.NextInt(); V = cin.NextInt(); Ox = cin.NextInt(); Oy = cin.NextInt(); L = new int[N][]; for (int i = 0; i < N; i++) { L[i] = cin.IntArray(); } var pq = new PriortyQueue(Compara); pq.Add(new Cell(1, 1, V)); B = new bool[N, N]; int oLife = -1; while (pq.Count > 0) { Cell c = pq.Poll(); B[c.Y - 1, c.X - 1] = true; if (c.Y == N && c.X == N) { Console.WriteLine("YES"); return; } if (c.Y == Oy && c.X == Ox) { oLife = c.Life; } for (int i = 0; i < 4; i++) { int nextY = c.Y + Next[i]; int nextX = c.X + Next[(i + 1) % 4]; if (nextX < 1 || nextY < 1) continue; if (nextX > N || nextY > N) continue; if (B[nextY - 1, nextX - 1]) continue; int nextLife = c.Life - L[nextY - 1][nextX - 1]; if (nextLife <= 0) continue; pq.Add(new Cell(nextX, nextY, nextLife)); } } if (Ox == 0 && Oy == 0) { Console.WriteLine("NO"); return; } pq = new PriortyQueue(Compara); pq.Add(new Cell(Ox, Oy, oLife*2)); B = new bool[N, N]; while (pq.Count > 0) { Cell c = pq.Poll(); B[c.Y - 1, c.X - 1] = true; if (c.Y == N && c.X == N) { Console.WriteLine("YES"); return; } for (int i = 0; i < 4; i++) { int nextY = c.Y + Next[i]; int nextX = c.X + Next[(i + 1) % 4]; if (nextX < 1 || nextY < 1) continue; if (nextX > N || nextY > N) continue; if (B[nextY - 1, nextX - 1]) continue; int nextLife = c.Life - L[nextY - 1][nextX - 1]; if (nextLife <= 0) continue; pq.Add(new Cell(nextX, nextY, nextLife)); } } Console.WriteLine("NO"); } private int Compara(Cell a, Cell b) { return a.Life.CompareTo(b.Life); } }