Finding a random WxH rectangle fitting in a MxN array region, where array[x][y] == number

Question

I'm programming a game where a random map is generated whenever a new game is started. The game field is a MxN boolean array (true=ground, false=air.) From that array I calculate each connected free (air) regions, generating a new MxN int array where the int value is 0 if there's is ground, or the region number if it's free space (each free space has the same region # as their neighbour free spaces.) Now my random playfield has been separated in numbered rooms.

E.g.:
Ground data:
000001100111000
000011000001110
000111000001111
000001110000001
000000011000011

Room data:
111110022000333
111100222220003
111000222220000
111110002222220
111111100222200

I need to populate these rooms with monsters, object, etc. so I need some way to find, given a rectangle size and a room #, a random place inside that room where the WxH rectangle would fit.

Obviously I could just blindly try random coordinates until the criteria is matched, but I don't think that's really the way to go, because it may take ages for the random number to meet the requirements (or not, it's random.)

I don't care if the random region is reusable later, I mean, I don't care if the same random region can be randomly selected twice (in other words, if objects spawn on top of other objects), but it would be preferable to be able to handle that situation too.

Thanks :)

Answer 1

You could make a list of valid positions for the objects (using logic similar to your room-determination algorithm), and randomly select an index into that list.

Answer 2

I would make a third MxN array that has a 0 or 1 in each spot. 0 means a WxH would not fit there and 1 means it would. This should be calculated at the same (or really, right after the time) you create the second array,