如何递归识别网格中特定类型的单元格？

Question

我正在学习 F# 并且正在构建一个扫雷应用程序。作为其中的一部分，我正在尝试一种方法，如果地雷被引爆，则递归地引爆所有相邻的地雷。所以如果我有一个像这样的网格：

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

然后我在 0,1 引爆地雷，它会依次引爆 1,2 的地雷，然后引爆 2,2 的地雷。 2,0 中的地雷不会引爆，因为它不与其他地雷相邻。

此时我实际上将该字段实现为列表：

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

我遇到的问题是如何从单元格 0,1 开始并以包含所有相邻地雷的列表结束。所以，我需要一个列表（只显示坐标）：

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

我可以毫不费力地获取特定位置的相邻地雷，然后从该组中确定地雷。

我遇到的麻烦 是如何让它以某种方式递归，直到附近没有发现地雷，然后给我一份我需要引爆的地雷的主列表。

一旦我得到地雷的主列表，我就可以引爆它们并建立一个更新的区域，让那些地雷变成弹坑。

更新 @Kevin 的回答有效，但我很难理解它。如果其他人也遇到困难，我将在下面添加功能，并进行评论和一些更改。

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 [])

proximity 函数（未显示）简单地包含了确定被测矿山是否为参考矿山、接近或远离参考矿山的逻辑。例如。 Self 如果当前单元格和地雷之间的距离为零，则返回 Self {Row=0, Column=0}。

Answer 1

好的，所以我不会 F#，所以我打算在 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

Answer 2

这将 return 一组所有引爆的电池，包括启动连锁反应的电池。

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 [])

如果您只想要一个像您问题中那样的位置列表，那么可以像这样轻松转换：

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

如何递归识别网格中特定类型的单元格？

How to recursively identify cells of specific type in grid?

recursion

f#

tail-recursion