Maksymalny obszar prostokąta bez potworów - algorytm, programowanie dynamiczne

Podano prostokątną siatkę N * M (1-punktowaindeksowanie), w którym są one k potworami na k różnych komórek. Teraz musimy odpowiedzieć na zapytania Q, w których otrzymamy najniższy numer wiersza (L) i najwyższy numer wiersza (H) musimy podać maksymalny obszar prostokąta między tymi wierszami które nie mają potwora (tutaj obszar prostokąta oznacza tylko liczbę komórek)

Przykład: Powiedzmy, że mamy siatkę 4 * 5 (średnia n = 4 im = 5), a potwory znajdują się na 7 (= k) komórkach, które są (1,3), (1,4), (2,1), (2,4), (3,2), (4,1), (4,2) i pozwólmy mieć 1 zapytanie, w którym L = 3 i H = 4, a maksymalny obszar wynosi tutaj 6.

Teraz, jeśli zapytania są bardzo duże, powiedzmy 10 ^ 6. Następnie, jak rozwiązać ten problem.

Tutaj czerwone bloki wskazują potwora, a fioletowy to prostokąt rozwiązania

Odpowiedzi:

Oto rekurencyjne rozwiązanie, które działa dla lochów o rozmiarze arbirary i stosunkowo niewielu potworów.

Jeśli w lochu jest jeden potwór (x, y) (n,w, s, e), są dwa przypadki. Przypadek 1 jest trywialny: potwór znajduje się poza lochem. Wtedy maksymalnym prostokątem jest loch. (Lochy są zawsze prostokątne, prawda?).

W przypadku 2 maksymalny prostokąt jest jednym z prostokątów na północ, zachód, południe lub wschód od potwora:

NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
NNNNNNNNNN    ....EEEEEE    ..........    WWW.......
...@......    ...@EEEEEE    ...@......    WWW@......
..........    ....EEEEEE    SSSSSSSSSS    WWW.......
..........    ....EEEEEE    SSSSSSSSSS    WWW.......
..........    ....EEEEEE    SSSSSSSSSS    WWW.......

Teraz zastosuj to rozumowanie rekurencyjnie dla swojej listy lokalizacji potworów i śledzić jak dotąd maksimum. Oto pseudo kod:

max_area = 0
max_rect = Null

sub find_max_rect(Dungeon, Monsters)

if area(Dunegon) <= max_area:
return                      # save time for small dungeons

if Monsters is empty:
if area(Dungeon) > max:
max_rect = Dungeon
max_area = area(Dungeon)

else
M = Monsters.pop()          # Remove head from list

if M in Dungeon:
find_max_rect(Subrect(Dungeon, M, North), Monsters)
find_max_rect(Subrect(Dungeon, M, East), Monsters)
find_max_rect(Subrect(Dungeon, M, South), Monsters)
find_max_rect(Subrect(Dungeon, M, West), Monsters)
else:
find_max_rect(Dungeon, Monsters)

Uwaga: faktycznie popełniłem rażący błąd w powyższych szkicach: @ reprezentuje oczywiście gracza, a nie potwora.

Czy znasz problem sumy maksymalnej macierzy? Ten problem można rozwiązać w czasie O (n ^ 3) przy użyciu programowania dynamicznego.

Twoje pytanie jest bardzo podobne do tego. Musisz przypisać każdą pustą wartość siatki 1 i każdą wartość siatki potworów -INF. Następnie po zastosowaniu rozwiązania sumy maksymalnej macierzy otrzymasz maksymalny obszar.