CODEWITHSUNDEEP
algorithmrecursiongeometry2ddynamic-programming
Sazzad Hissain Khan
Sazzad Hissain Khan

Reputation: 40166

Algorithm required for maximizing number of squares fitting in rectangle with constraints

I need an algorithm which counts the maximum possible number of squares of length X which can be fitting inside a M x N rectangle with constraints of grid availability.

For example when X = 2 and M = N = 8 (gray grids cannot be used)

gray grids cannot be used

We get maximum 10 squares fitting inside this rectangle. like below solution there may be multiple solution spaces for maximum count.

enter image description here

  1. Which algorithm can do it for me?
  2. Is there any DP solution unlike polynomial?
  3. Is there any name of such particular algorithm?

[NB: I assume greedy wont work here, if i am wrong correct me]

Let please describe whatever the best approach you know.

Upvotes: 2

Views: 452

Answers (1)

AlexAlvarez
AlexAlvarez

Reputation: 829

As requested, for X = 2 you can use DP with bitmasks. You can either proceed by columns or rows, so you usually take the smaller one. Let's assume that the minimum number is the number of columns.

You can do a DP in which the state is the current row, the current column and a bitmask telling which columns are blocked in the current row.

Let me explain it a bit with your example.

Original state: row = 0, column = 0, bitmask = 00000000.

Check if you can place a square in your current position, in this case you can. So the result will be max(1 + placing the square, not placing the square). If you can't, then you only have one option: not placing it.

In case you don't place the square, your next state is row = 0, column = 1, bitmask = 00000000. Notice that now the first bit is telling about the next row, not the current as we have already passed that column.

In case you place the square, your next state is row = 0, column = 2 (we jump two because of the square) and bitmask = 11000000. That bitmask tells you that the first two positions of the second row are already blocked.

Now let's consider a different state, row = 2, column = 4, bitmask = 11110000. This corresponds to the case of your solution when you are in the third row and the fifth column. The bitmask tells us that the four first cells of the next row are already blocked and that the four next cells of the current row are free.

So again, you check if you can place or not the square. The cells are not blocked, but the grid contains a marked cell, so you can't. The next state is then row = 2, column = 5, bitmask = 11110000. With that example I want you to notice that the bitmask doesn't tell you anything about cells blocked by the original grid, but just by your previous squares.

So every state is checked in constant time, thus the complexity of the algorithm is the number of states, which is O(NM * 2^(min(N, M))), sorry I forgot an extra factor in my comment.

Upvotes: 2

Related Questions