· haskell algorithms

Algorithms: Flood Fill in Haskell

Flood fill is an algorithm used to work out which nodes are connected to a certain node in a multi dimensional array. In this case we’ll use a two dimensional array.

The idea is that we decide that we want to change the colour of one of the cells in the array and have its immediate neighbours who share its initial colour have their colour changed too i.e. the colour floods its way through the grid.

The algorithm is described on Wikipedia like so:

Flood-fill (node, target-color, replacement-color):

  1. If the color of node is not equal to target-color, return.

  2. Set the color of node to replacement-color.

    • Perform Flood-fill (one step to the west of node, target-color, replacement-color).

    • Perform Flood-fill (one step to the east of node, target-color, replacement-color).

    • Perform Flood-fill (one step to the north of node, target-color, replacement-color).

    • Perform Flood-fill (one step to the south of node, target-color, replacement-color).

  4. Return.replacehttp://cvs.haskell.org/Hugs/pages/libraries/base/Data-Array.html#v%3AboundstoComplexArrayhttps://github.com/mneedham/haskell/blob/master/PrintArray.hsprintGridhttp://www.markhneedham.com/blog/2012/04/03/haskell-print-friendly-representation-of-an-array/[in my last post]my github haskell repository

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket