Flood fill

floodfill.scala

/**
 * Flood Fill
 * Given a matrix a containing numbers that represents a 
 * labyrinth with empty space and walls, as follows: 
 * 0 is empty space, 1 is a wall, and 2 is water.
 *
 * Write a program that fills the labyrinth with water starting 
 * from a given position given by coordinates x and y, 
 * The top-left coordinate of the matrix is 0,0.
 * ```
 * Input:
 * a = [[1, 1, 1, 1, 1, 1]
 *      [1, 0, 0, 1, 0, 1]
 *      [1, 1, 0, 1, 1, 1]
 *      [1, 0, 0, 0, 0, 1]
 *      [1, 1, 1, 1, 1, 1]]
 * x = 1
 * y = 1
 * 
 * Output:
 * a = [[1, 1, 1, 1, 1, 1]
 *      [1, 2, 2, 1, 0, 1]
 *      [1, 1, 2, 1, 1, 1]
 *      [1, 2, 2, 2, 2, 1]
 *      [1, 1, 1, 1, 1, 1]]
 * ```
 */

object floodfill {
  import scala.collection.mutable.ArrayBuffer

  val a = ArrayBuffer(
     ArrayBuffer(1, 1, 1, 1, 1, 1),
     ArrayBuffer(1, 0, 0, 1, 0, 1),
     ArrayBuffer(1, 1, 0, 1, 1, 1),
     ArrayBuffer(1, 0, 0, 0, 0, 1),
     ArrayBuffer(1, 1, 1, 1, 1, 1)
  )

  def main(args: Array[String]):Unit = {
    val arr = ArrayBuffer.fill(1, 1)(0)
    fill(arr, 0, 0)
    println(arr.map(_.mkString("[", ",", "]")).mkString)
    fill(a, 1, 1)
    println(a.map(_.mkString("[", ",", "]")).mkString("\n"))
  }
  
  var visited: Set[(Int, Int)] = Set()
  
  def checkAndFill(arr: ArrayBuffer[ArrayBuffer[Int]], x: Int, y: Int): Unit = {
    val needToVisit = arr(x)(y) == 0 && !visited.contains((x, y))
    if (needToVisit) {
      visited += ((x, y))
      fill(arr, x, y)
    }
  }
  
  def fill(arr: ArrayBuffer[ArrayBuffer[Int]], x: Int, y: Int): Unit = {
    if (arr(x)(y) == 0) arr(x)(y) = 2
    if (y > 0) checkAndFill(arr, x, y - 1) // top
    if (x > 0) checkAndFill(arr, x - 1, y) // left
    if (y + 1 < arr(0).size) checkAndFill(arr, x, y + 1) // bottom
    if (x + 1 < arr(0).size) checkAndFill(arr, x + 1, y) // right
  }
}