имеется двумерный массив, заполненый 1 и 0. по сути — это бинарное изображение, где 0 — это черные пиксели, а 1 — белые. само изображение организовано так, что белые пиксели организованы по группам, которые разделены между собой черными пикселями (стенками).
задача: найти белые пятна на картинке и каждое пятно маркиковать отдельным числом. например, на картинке 3 белых пятна, разделенные черными стенками. то есть в итоговой картинке каждое пятно (состоящее из белых пикселей) обозначено числами 2, 3, 4 и так далее. реализован данный алгоритм так
// Learn more about F# at http://fsharp.org
open System
let source = array2D [[1; 1; 0; 1; 1; 1; 0; 1];
[1; 1; 0; 1; 0; 1; 0; 1];
[1; 1; 1; 1; 0; 0; 0; 1];
[0; 0; 0; 0; 0; 0; 0; 1];
[1; 1; 1; 1; 0; 1; 0; 1];
[0; 0; 0; 1; 0; 1; 0; 1];
[1; 1; 0; 1; 0; 0; 0; 1];
[1; 1; 0; 1; 0; 1; 1; 1]]
let (|Value|Zero|Out|) ((x: int), (y: int)) =
if x < 0 || y < 0 || x > (source.[0,*].Length - 1) || y > (source.[*,0].Length - 1) then
Out
else
let row = source.[y, *]
match row.[x] with
| 0 -> Zero
| v -> Value(v)
let processSource x y value =
let rec markBits x y value =
match (x, y) with
| Value(v) ->
if v <> value then
source.[y, x] <- value
markBits (x + 1) y value
markBits (x - 1) y value
markBits x (y + 1) value
markBits x (y - 1) value
| Zero | Out -> ()
markBits x y value
[<EntryPoint>]
let main argv =
printfn "Hello World from F#!"
printfn "origin"
printfn "%A" source
printfn "--------------"
let mutable value = 2
source
|> Array2D.iteri (fun y x e -> if e = 1 then
processSource x y value
value <- value + 1)
printfn "modified"
printfn "%A" source
0 // return an integer exit code
результат работы такой
Hello World from F#!
origin
[[1; 1; 0; 1; 1; 1; 0; 1]
[1; 1; 0; 1; 0; 1; 0; 1]
[1; 1; 1; 1; 0; 0; 0; 1]
[0; 0; 0; 0; 0; 0; 0; 1]
[1; 1; 1; 1; 0; 1; 0; 1]
[0; 0; 0; 1; 0; 1; 0; 1]
[1; 1; 0; 1; 0; 0; 0; 1]
[1; 1; 0; 1; 0; 1; 1; 1]]
--------------
modified
[[2; 2; 0; 2; 2; 2; 0; 3]
[2; 2; 0; 2; 0; 2; 0; 3]
[2; 2; 2; 2; 0; 0; 0; 3]
[0; 0; 0; 0; 0; 0; 0; 3]
[4; 4; 4; 4; 0; 5; 0; 3]
[0; 0; 0; 4; 0; 5; 0; 3]
[6; 6; 0; 4; 0; 0; 0; 3]
[6; 6; 0; 4; 0; 3; 3; 3]]
по задумке, функция processSource реализована по принцицам хвостовой рекурсии, однако отладчик показывает, что каждый вызов рекурсивной функции markBits добавляет новый кадр в стек. то есть хвостовая рекурсия не работает. не могу понять, почему? ведь задача каждого кадра — всего лишь отметить очередной пиксель нужным числом и вызвать такую же функцию для всех соседних пикселей. сам кадр рекурсии обратно ничего не вычисляет и не возвращает. то есть компилятору нет смысла делать обычную рекурсию.
в чем ошибка? спасибо
