矩形无任何妖怪最大面积 [英] Maximum Area of rectangle without any monsters
问题描述
鉴于N * M（基于1的索引），其中他们的k个怪物上k个不同cells.Now我们需要回答查询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.Then如何解决这个problem.Is他们的任何动态的方式左右做呢？
下面的红色方块表示的怪物，紫色的是解决方案的矩形
下面是一个递归的解决方案，适用于arbirary大小的地牢和相对较少的怪物。
如果有一个怪物（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 .......
现在递归地应用这种推理为你的怪物的地点列表，并跟踪最大为止。下面是一些伪code：
max_area = 0
max_rect = NULL
子find_max_rect（地下城，怪物）
如果区域（Dunegon）＆LT; = max_area：
返回＃保存时间为小型地下城
如果怪物是空的：
如果区域（地下城）＆GT;最大：
max_rect =地牢
max_area =区域（地下城）
其他
M = Monsters.pop（）从列表中删除＃头
如果M在地下城：
find_max_rect（Subrect（地下城，男，北），怪兽）
find_max_rect（Subrect（地下城，男，华东），怪兽）
find_max_rect（Subrect（地下城，男，南），怪兽）
find_max_rect（Subrect（地下城，男，西），怪兽）
其他：
find_max_rect（地下城，怪物）
注：其实我已经做了一个明显的错误，在草图上图： @ 重presents，当然，球员而不是一个怪物
Given a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells.Now we need to answer Q queries in which we will be given lowest row number(L) and highest row number(H) we need to tell maximum area of rectangle between those rows that don't have a monster.(Here area of rectangle means count of cells only)
Example : Say we have a grid of 4 * 5 (mean n=4 and m=5) and monsters are located on 7(=k) cells which are (1,3) , (1,4) , (2,1) , (2,4) , (3,2) , (4,1) , (4,2) and let we have 1 query in which L=3 and H=4 then the maximum area is 6 here.
Now if the queries are very large say 10^6.Then how to tackle this problem.Is their any dynamic approach or so for doing it?
Here red blocks indicate monster and purple one is solution rectangle
Here's a recursive solution that works for dungeons of arbirary size and relatively few monsters.
If there is one monster (x, y) in the dungeon (n, w, s, e), there are two cases. Case 1 is trivial: The monster is outside the dungeon. Then the maximum rectangle is the dungeon. (Dungeons are always rectangular, right?).
In Case 2, the maximum rectangle is one of the rectangles north, west, south or east of the monster:
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.......
Now apply this reasoning recursively for your list of monster locations and keep track of the maximum so far. Here's some pseudo code:
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)
Note: I've actually made a glaring mistake in the sketches above: @ represents, of course, the player and not a monster.
这篇关于矩形无任何妖怪最大面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
