algorithm - 没有任何怪物的矩形的最大面积

Question

给定一个 N*M(基于 1 的索引)的矩形网格，其中它们是 k 个不同单元格上的 k 个怪物。现在我们需要回答 Q 个查询，其中我们将获得最低行号(L)和最高行number(H) 我们需要告诉那些没有怪物的行之间的最大矩形面积。(这里的矩形面积仅表示单元格数)

示例:假设我们有一个 4 * 5 的网格(平均 n=4 和 m=5)并且怪物位于 7(=k) 个单元格上，这些单元格是 (1,3) , (1,4) , ( 2,1) , (2,4) , (3,2) , (4,1) , (4,2) 让我们有 1 个查询，其中 L=3 和 H=4 那么这里的最大面积是 6 .

现在，如果查询非常大，比如 10^6。那么如何解决这个问题。他们是否采用任何动态方法来解决这个问题？

这里红色方 block 表示怪物，紫色方 block 是解决方 block

Answer 1

这是一个适用于任意大小和相对较少怪物的地牢的递归解决方案。

如果地牢(n, w, s, e)中只有一只怪物(x, y)，则有两种情况。情况 1 很简单:怪物在地牢外面。那么最大的矩形就是地牢。 (地下城总是矩形的，对吧？)。

在情况2中，最大矩形是怪物北、西、南或东的矩形之一:

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

现在对您的怪物位置列表递归应用此推理，并跟踪到目前为止的最大值。这是一些伪代码:

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)

注意:实际上我在上面的草图中犯了一个明显的错误:@ 当然代表玩家而不是怪物。