import scala.collection.mutable.Queue import scala.math._ object Main { def bfs(vitality: Int, start: (Int, Int), goal: (Int, Int), g: Array[Array[Int]]): Int = { val N = g.size val q = new Queue[(Int, Int, Int, Int)] // (row, col, vitality, step) q.enqueue((start._1, start._2, vitality, 0)) val memo = Array.ofDim[Int](N, N) while (!q.isEmpty) { val (row, col, v, step) = q.dequeue // println(row, col) if (row == goal._1 && col == goal._2) return step if (memo(row)(col) == 0 || memo(row)(col) < v) { memo(row)(col) = v 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) { val v2 = v - g(r)(c) if (v2 > 0 && (memo(r)(c) == 0 || memo(r)(c) < v)) { q.enqueue((r, c, v - g(r)(c), step + 1)) } } } } } return -1 } def main(args: Array[String]) { val sc = new java.util.Scanner(System.in) val n, v, sx, sy, gx, gy = 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 ans = bfs(v, (sy-1, sx-1), (gy-1, gx-1), g) println(ans) } }