Я изучаю 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
возвращается, если расстояние между текущей ячейкой и шахтой равно нулю {Row=0, Column=0}.