Maximum Area of rectangle without any monsters

Question

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

@P0W i dont get what u wanna say.In the solution rectangle we can see their is no monster — user3086701
@user3086701 Please remove the question because it is same as problem in codechef ongoing long contest codechef.com/JAN14/problems/METEORAK . I am not blaming you for cheating — Vikram Bhat
@VikramBhat: No. Well, maybe a bit. I took the question to be about a role-playing game, a typical newbie programming exercise. (You have to give the OP credit for camouflaging the question well.) Anyway, the problem of the effective algo hasn't been solved here and people seem to have lost interest in the question. No hard feelings. — M Oehm

M Oehm M Oehm · Accepted Answer · 2014-01-05T20:41:22

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.

Maximum Area of rectangle without any monsters

2 Answers