0

ATTENTION: this is not maximal rectangle problem. this is about number of rectangles.

look at this picture: enter image description here

I am looking for an algorithm to compute total number of blue rectangles(not maximal rectangle). this algorithm must be O(n^2) and we have a constraint that the board is Square(n*n) or in this picture m=n.

thanks in advance

jahande
  • 69
  • 9
  • 1
    See http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf – BadZen Nov 12 '16 at 17:14
  • 3
    You'd better post at least your initial attempt, and point out its flaws and ask for enhancements, because without showing a minimum effort, you'll hardly get an answer. – Little Santi Nov 12 '16 at 17:25
  • Well, one way would be repeatedly find max rectangle until you can't find anymore rectangles. And squares are geometrically rectangles, so count each shaded cell as well – OneCricketeer Nov 12 '16 at 17:43
  • So is your question "how many distinct blue rectangles there are"? The picture you attached is from the maximal rectangle problem... – kgf3JfUtW Dec 01 '16 at 22:46

0 Answers0