给出了n*m（1-基索引）的矩形网格，其中它们是k个不同单元上的k个怪物。现在我们需要回答Q查询，其中我们将给出最低行数（L）和最高行数（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。那么如何解决这个问题。他们有什么动态的方法吗？
红色方块表示怪物，紫色方块表示解决方案矩形
最佳答案
这是一个递归的解决方案，适用于任意大小的地下城和相对较少的怪物。
如果地牢里有一个怪物（x，y）（n，w，s，e），那么就有两个例子案例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)
注：实际上我在上面的草图中犯了一个明显的错误：
@代表的当然是玩家而不是怪物。