Let's say that I'm given a $n\times n$ ($n\leq 1000$) grid (more of like a table) and I color the grid with $n^2$ rectangles, each of a different color (let's say they have colors 1 to $n^2$ for simplicity). The color of the rectangle that is colored the latest on a cell will remain that color. For example, I could have the following progression:0 0 00 0 00 0 01 1 01 1 00 0 01 1 01 2 20 2 21 1 31 2 30 2 3Of course, the example would continue for all $n^2$ colors, and you are only given the final state as the input. For example, the input we would be given is only the last grid of the 4 above. From it, you have to determine, what is the number of possible colored rectangles that could have been painted first?My initial idea is that any rectangle that overlaps another rectangle cannot be the bottommost. For example, in the sample, we know that color 2 cannot be the bottommost because it covers color 1. On the other hand, color 1 and color 3 do not cover any other colors, so they can be the bottommost. I suspect that this can lead to an algorithm, but how?
Finding all possible bottom-most overlapping rectangles on a table
algorithms;counting