Implement a flood fill.

A flood fill is a way of filling an area using color banks to define the contained area or a target color which "determines" the area (the valley that can be flooded; Wikipedia uses the term target color). It works almost like a water flooding from a point towards the banks (or: inside the valley): if there's a hole in the banks, the flood is not contained and all the image (or all the "connected valleys") get filled.

To accomplish the task, you need to implement just one of the possible algorithms (examples are on Wikipedia). Variations on the theme are allowed (e.g. adding a tolerance parameter or argument for color-matching of the banks or target color).

 
Testing: the basic algorithm is not suitable for truecolor images; a possible test image is the one shown on the right box; you can try to fill the white area, or the black inner circle.

(* For simplicity, we're going to fill black-and-white images. Nothing
 * fundamental would change if we used more colors. *)
datatype color = Black | White
(* Represent an image as a 2D mutable array of pixels, since flood-fill
 * is naturally an imperative algorithm. *)
type image = color array array
 
(* Helper functions to construct images for testing. Map 0 -> White
 * and 1 -> Black so we can write images concisely as lists. *)
fun intToColor 0 = White
  | intToColor _ = Black
 
fun listToImage (LL : int list list) : image =
    Array.tabulate(List.length LL,
     fn i => Array.tabulate (List.length (hd LL),
       fn j => intToColor(List.nth(List.nth(LL,i),j))))
 
(* Is the given pixel within the image ? *)
fun inBounds (img : image) ((x,y) : int * int) : bool =
    x >= 0 andalso y >= 0 andalso y < Array.length img
    andalso x < Array.length (Array.sub(img, y))
 
(* Return an option containing the neighbors we should explore next, if any.*)
fun neighbors (img : image) (c : color) ((x,y) : int * int) : (int * int) list option =
    if inBounds img (x,y) andalso Array.sub(Array.sub(img,y),x) <> c
    then SOME [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    else NONE
 
(* Update the given pixel of the image. *)
fun setPixel (img : image) ((x,y) : int * int) (c : color) : unit =
    Array.update (Array.sub(img,y),x,c)
 
(* Recursive fill around the given point using the given color. *)
fun fill (img : image) (c : color) ((x,y) : int * int) : unit =
    case neighbors img c (x,y) of
        SOME xys => (setPixel img (x,y) c; List.app (fill img c) xys)
      | NONE => ()
 
val test = listToImage
[[0,0,1,1,0,1,0],
 [1,0,1,0,1,0,0],
 [1,0,0,0,0,0,1],
 [0,1,0,0,0,1,0],
 [1,0,0,0,0,0,1],
 [0,0,1,1,1,0,0],
 [0,1,0,0,0,1,0]]
 
(* Fill the image with black starting at the center. *)
val () = fill test Black (3,3)