Próbowałem znaleźć rozwiązanie mojego problemu przez ponad tydzień i nie mogłem znaleźć niczego lepszego niż milion progów iteracji, więc myślę, że nadszedł czas, aby poprosić kogoś o pomoc.

Mam tablicę 3D. Powiedzmy, że mówimy o ziemi, a pierwsza warstwa jest powierzchnią. Kolejne warstwy to podłogi pod ziemią. Muszę znaleźć najgłębszą długość ścieżki, liczbę pojedynczych jaskiń pod ziemią i wielkość największej jaskini.

Oto wizualizacja mojego problemu.

Input:
5 5 5 // x, y, z
xxxxx
oxxxx
xxxxx
xoxxo
ooxxx

xxxxx
xxoxx

and so...

Output:
5 // deepest path - starting from the surface
22 // size of the biggest cave
3 // number of izolated caves (red ones) (izolated - cave that doesn't reach the surface)

Zauważ, że nawet jeśli czerwona komórka na drugim piętrze jest umieszczona obok zielonej, to nie jest to ta sama jaskinia, ponieważ jest umieszczona po przekątnej i to się nie liczy. Powiedziano mi, że najlepszym sposobem na to może być użycie algorytmu rekurencyjnego „dziel i rządź”, ale tak naprawdę nie wiem, jak mogłoby to wyglądać.