Maximale Fläche des Rechtecks ​​ohne Monster - Algorithmus, dynamische Programmierung

Gegeben ein rechteckiges Gitter von N * M (1-basiertIndexierung), in der sie sind k Monster auf k verschiedenen Zellen.Nun müssen wir beantworten Q Fragen, in denen uns die niedrigste Reihe Nummer (L) und höchste Reihe Nummer (H) müssen wir maximale Fläche des Rechtecks ​​zwischen diesen Zeilen sagen die kein Monster haben. (Hier bedeutet der Bereich des Rechtecks ​​nur die Anzahl der Zellen)

Beispiel: Angenommen, wir haben ein Gitter von 4 * 5 (Mittelwert n = 4 und m = 5) und Monster befinden sich auf 7 (= k) Zellen, die (1,3), (1,4), (2,1) sind. (2,4), (3,2), (4,1), (4,2) und wir haben 1 Abfrage, in der L = 3 und H = 4, dann ist hier die maximale Fläche 6.

Nun, wenn die Abfragen sehr groß sind, sagen wir 10 ^ 6. Dann, wie man dieses Problem angeht. Ist ihr irgendein dynamischer Ansatz oder so dafür?

Hier zeigen rote Blöcke Monster an und lila ist das Lösungsrechteck

Antworten:

Hier ist eine rekursive Lösung, die für Dungeons von beliebiger Größe und relativ wenigen Monstern funktioniert.

Wenn es ein Monster (x, y) im Verlies gibt (n,w, s, e), gibt es zwei Fälle. Fall 1 ist trivial: Das Monster befindet sich außerhalb des Verlieses. Dann ist das maximale Rechteck der Dungeon. (Dungeons sind immer rechteckig, oder?).

In Fall 2 ist das maximale Rechteck eines der Rechtecke nördlich, westlich, südlich oder östlich des Monsters:

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.......

Nun wenden Sie diese Argumentation rekursiv für Ihre Liste von Monsterstandorten an und behalten Sie das Maximum bis jetzt im Auge. Hier ist ein Pseudocode:

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)

Hinweis: Ich habe in den obigen Skizzen einen eklatanten Fehler gemacht: @ stellt natürlich den Spieler und kein Monster dar.

Kennen Sie das Problem der maximalen Matrixsumme? Dieses Problem kann in O (n ^ 3) -Zeit mit dynamischer Programmierung gelöst werden.

Ihre Frage ist dem sehr ähnlich. Sie müssen jedem leeren Rasterwert 1 und jedem Monsterrasterwert -INF zuweisen. Nachdem Sie die Lösung mit der maximalen Matrixsumme angewendet haben, erhalten Sie die maximale Fläche.