CODEWITHSUNDEEP
algorithmdynamic-programming
user3086701
user3086701

Reputation: 63

Maximum Area of rectangle without any monsters

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?

enter image description here

Here red blocks indicate monster and purple one is solution rectangle

Upvotes: 0

Views: 982

Answers (2)

songlj
songlj

Reputation: 927

Do you know maximum matrix sum problem? That problem can be solved in O(n^3) time using dynamic programming.

Your question is very similar to that. What you need is to assign every empty grid value 1 and every monster grid value -INF. Then after you apply the maximum matrix sum solution, you got the maximum area.

Upvotes: 0

M Oehm
M Oehm

Reputation: 29136

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.

Upvotes: 1

Related Questions