Vanya.scala

import scala.collection.mutable.ArrayBuffer
import scala.io.StdIn

case class Pos(row: Int, col: Int)
case class Key(pos: Pos, distance: Int)

object Vanya {

  def distance(p1: Pos, p2: Pos): Int = (p1.row - p2.row).abs + (p1.col - p2.col).abs

  def main(args: Array[String]): Unit = {

    val Array(n, m, p) = StdIn.readLine().split("\\s+").map(_.toInt)
    val keys: Array[ArrayBuffer[Key]] = Array.fill(p+1)(ArrayBuffer.empty)
    var currentLevel = 0
    var row = 0

    keys(0) += Key(Pos(0,0), 0)
    while (row < n) {
      val cols = StdIn.readLine().split("\\s+").map(_.toInt)
      var col = 0

      while (col < m) {
        keys(cols(col)) += Key(Pos(row, col), Int.MaxValue)
        col += 1
      }
      row += 1
    }


    while (currentLevel < p) {
      val fromKeys = keys(currentLevel)
      val nextLevel = currentLevel + 1

      var current = 0
      while (current < fromKeys.size) {
        val toCurrentDistance = fromKeys(current).distance
        val currentPos = fromKeys(current).pos
        val nextKeys = keys(nextLevel)

        var next = 0
        while (next < nextKeys.size) {
          val nextPos = nextKeys(next).pos
          val previousNextDistance = nextKeys(next).distance
          val fromCurrentToNextDistance = distance(currentPos, nextPos)
          val toNextDistance  = toCurrentDistance + fromCurrentToNextDistance

          if (toNextDistance < previousNextDistance)
            nextKeys(next) = Key(nextPos, toNextDistance)
          next += 1
        }
        current += 1
      }
        currentLevel += 1
    }
    println(keys(p).head.distance)
  }

}