import scala.collection.mutable.PriorityQueue import scala.collection.mutable.HashSet import scala.math._ object Main { def Ord = new Ordering[(Int, Int, Int)] { // (row, col, cost) def compare(a: (Int, Int, Int), b: (Int, Int, Int)): Int = b._3.compare(a._3) } def dijkstra(start: (Int, Int), goal: (Int, Int), g: Array[Array[Int]]): Int = { val N = g.size val q = new PriorityQueue[(Int, Int, Int)]()(Ord) // (row, col, cost) q.enqueue((start._1, start._2, 0)) val used = new HashSet[(Int, Int)] while (!q.isEmpty) { val (row, col, cost) = q.dequeue if (row == goal._1 && col == goal._2) return cost if (!used.contains((row, col))) { used.add((row, col)) for (i <- -1 to 1; j <- -1 to 1 if abs(i) + abs(j) == 1) { val r = row + i val c = col + j if (0 <= r && r < N && 0 <= c && c < N) { if (!used.contains((r, c))) { q.enqueue((r, c, cost + g(r)(c))) } } } } } assert(false, "can not reach goal") return 0 } def calc(n: Int, vitality: Int, oasis: (Int, Int), g: Array[Array[Int]]): Boolean = { // オアシス経由せずにいける if (vitality > dijkstra((0, 0), (n-1, n-1), g)) { return true } // オアシスは存在しない if (oasis._1 == -1 && oasis._2 == -1) return false // オアシス経由する val a = dijkstra((0, 0), oasis, g) // スタートからオアシスまでのコスト if (vitality > a) { // オアシスまでたどり着ける val v = (vitality - a) * 2 // 体力回復 if (v > dijkstra(oasis, (n-1, n-1), g)) { // オアシスからゴールにたどり着ける return true } } return false } def main(args: Array[String]) { val sc = new java.util.Scanner(System.in) val n, v, ox, oy = sc.nextInt val g = Array.ofDim[Int](n, n) for (i <- 0 to n-1) { for (j <- 0 to n-1) { g(i)(j) = sc.nextInt } } val reachable = calc(n, v, (oy-1, ox-1), g) if (reachable) println("YES") else println("NO") } }