find all rectangular areas with certain properties in a matrix

Question

given an n*m matrix with the possible values of 1, 2 and null:

  . . . . . 1 . .
  . 1 . . . . . 1
  . . . 2 . . . .
  . . . . 2 . . .
  1 . . . . . 1 .
  . . . . . . . .
  . . 1 . . 2 . .
  2 . . . . . . 1

I am looking for all blocks B (containing all values between (x0,y0) and (x1,y1)) that:

• contain at least one '1'
• contain no '2'
• are not a subset of a another block with the above properties

Example:

The red, green and blue area all contain an '1', no '2', and are not part of a larger area. There are of course more than 3 such blocks in this picture. I want to find all these blocks.

what would be a fast way to find all these areas?

I have a working brute-force solution, iterating over all possible rectangles, checking if they fulfill the first two criteria; then iterating over all found rectangles, removing all rectangles that are contained in another rectangle; and I can speed that up by first removing consecutive identical rows and columns. But I am fairly certain that there is a much faster way.

Answer 1

You can get somewhere between considering every rectangle, and a properly clever solution.

For example, starting at each 1 you could create a rectangle and gradually expand its edges outwards in 4 directions. Stop when you hit a 2, record this rectangle if (a) you've had to stop in all 4 directions, and (b) you haven't seen this rectangle before.

Then backtrack: you need to be able to generate both the red rectangle and the green rectangle starting from the 1 near the top left.

This algorithm has some pretty bad worst cases, though. An input consisting of all 1s springs to mind. So it does need to be combined with some other cleverness, or some constraints on the input.