How to recursively identify cells of specific type in grid?

Question

I'm learning F# and I'm building a minesweeper app. As part of that, I'm trying to have a method that detonates all adjacent mines if a mine is detonated, recursively. So if I have a grid like:

     |  0  |  1  |  2  |
------------------------
  0  | E-1 |  M  | E-2 |
  1  | E-2 | E-4 |  M  |
  2  |  M  | E-3 |  M  |

and I detonate the mine in 0,1, it would in turn detonate the mine in 1,2 and that would in turn detonate the mine in 2,2. The mine in 2,0 would not detonate because it isn't adjacent to any of the others.

At this point I've actually implemented the field as a list:

module CellContents =
  type T = 
    | Empty of int
    | Mine
    | Crater

module Location =
  type T = { Row: int; Column: int }

module Cell =
  type T = 
    { Content : CellContents.T
      Location : Location.T }

module Field =
  type T = Cell.T list

What I'm having trouble with is how to start with cell 0,1 and the end up with a list of all mines that are adjacent. So, I need a list like (showing just coordinates):

let minesToDetonate = [ {Row=0;Column=1};{Row=1;Column=2};{Row=2;Column=2} ]

I have no trouble getting the adjacent mines for a specific location and then determining the mines from that group.

What I'm having trouble with is getting this to recurse somehow and go until there are no mines found adjacent, giving me a master list the mines I need to detonate.

Once I get the master list of mines, I can detonate them and build an updated field with those mines becoming craters.

Update @Kevin's answer worked, but I had a hard time understanding it. In case others also have a hard time, I'm adding the function below, with comments and a couple of changes.

let detonateProximity (field:T) (start:Cell.T) =
    let rec inner cells m acc =
        match cells with
        | [] -> acc
        | x::xs -> 
            match x.Content with
            |Mine ->
              match proximity m.Location x.Location with
              // Continue but don't accumulate
              | Self -> inner xs m acc
              | Near -> 
                  // See if current cell has already been found
                  match acc |> List.tryFind (fun t -> t = x) with
                  // If it has, we're done. Pass out
                  // an empty list which ends recursion.
                  |Some _ -> [] 
                  // If it wasn't found (this parts hurts my brain)...
                  // calls function once for rest field and then
                  // using new starting point on whole field.
                  // Is this efficient at all?
                  |None -> List.concat [(inner xs m (x::acc));(inner field x (x::acc))]
              // Don't accumulate, continue with rest of mines.
              | Far -> inner xs m acc
            // Not a mine, keep going, don't accumulate
            |_ -> inner xs m acc

    // The set ensures no duplicates
    Set.ofList (inner field start [])

The proximity function (not shown) simply wraps up the logic that determines if the tested mine is the reference mine, close to it or far from it. E.g. Self is returned if the distance between the current cell and the mine is zero {Row=0, Column=0}.

Answer 1

This will return a set of all detonated cells including the one that started the chain reaction.

module Location =
  type T = {Row: int; Column: int }

  let subtract l1 l2 =
      {Row=l1.Row - l2.Row;Column=l1.Column-l2.Colum

let detonate (field:Field.T) (start:Cell.T) =
  let rec inner cells m acc =
    match cells with
    | [] -> acc
    | x::xs -> match x.Content with
               |Mine ->match subtract m.Location x.Location with
                       |{Row = 0;Column = 0} -> inner xs m acc
                       |loc when abs (loc.Row) < 2 && abs (loc.Column) < 2 -> 
                          match acc |> List.tryFind (fun t -> t = x) with
                          |Some _ -> [] 
                          |None -> List.concat [(inner xs m (x::acc));(inner field x (x::acc))]
                       | _ -> inner xs m acc
               |_ -> inner xs m acc
  Set.ofList (inner field start [])

If you just want a list of locations like in your question its easy to convert like so:

detonate board {Content=Mine;Location={Row=0;Column=1}}
  |> Set.map (fun t -> t.Location)
  |> Set.toList

Answer 2

Ok, so I don't know F#, so I'm going to write this in Python.

def getDetonationList ( startingWithThisCell ) :
    seen = set()
    current = set ( [startWithThisCell] )
    while current :
        # Get all the mine cells that are adjacent to every ones
        # we are currently exploring. Then remove the ones we're
        # currently exploring and the ones we've seen, just so
        # we don't duplicate effort later.
        nearby = allMinesAdjacentToCells(current) - seen - current

        # Mark that we've seen the current ones (add the current
        # ones to the overall seen ones
        seen.update ( current )

        # Now we start over, starting from the newly found mines
        current = nearby
        # Note that if this is empty, this list will end, which
        # means that we will have seen as many as we could have
        # seen.
    return seen