我需要一种算法，计算长X的可装配一个M×N个矩形内与电网可用性约束平方的最大可能数。

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.

例如 当X = 2和M = N = 8（灰色网格不能使用）

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

我们获得最大的10平方这个矩形内配合。 如下面的解决方案有可能是最大计数多解的空间。

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

在哪些算法可以做到这一点对我？ 有不同的多项式？任何DP解决方案 有没有这样的特定算法的任何名称？ Which algorithm can do it for me? Is there any DP solution unlike polynomial? 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.

推荐答案

根据要求，为的 X = 2，您可以使用DP与位掩码。您可以继续通过列或行，所以你通常需要较小的一个。假设的最小数目是列数

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.

您可以做一个DP所处的状态是当前行，当前列，哪些列被封锁当前行中的位掩码说明问题。

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.

原始状态：行= 0，列= 0，掩码= 00000000

检查，如果你可以把一个正方形你的当前位置，在这种情况下，你可以。因此，其结果将是 MAX（1 +放置方，也不能放置平方）。如果你不能，那么你只有一个选择：不是把它放在

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.

如果你不把广场上，你的下一个状态是行= 0，列= 1，位掩码= 00000000 。请注意，现在第一位讲述的下一行，而不是目前我们已经通过了列。

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.

如果你把广场上，你的下一个状态是行= 0，列= 2 （因为方的我们跳到二）和掩码= 11000000 。该位掩码告诉你，第二行的前两个位置都已经封锁。

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.

现在，让我们考虑一个不同的状态，行= 2，列= 4，掩码= 11110000 。这对应于您的溶液的情况下，当你的第三行和第五列在。该位掩码告诉我们，下一行的四个第一单元已经堵塞，并且当前行的下一个四个单元是空闲的。

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.

所以，再一次，你检查你是否能到位与否的平方。这些细胞不会被阻止，但网格包含一个显着的细胞，所以你不能。下一个状态是那么​​行= 2，列= 5位掩码= 11110000 。通过这个例子我希望你能注意到位掩码不会告诉你的细胞已被原来的网格什么，但只是通过你的previous广场。

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.

所以，每个国家都在固定时间内检查，因此该算法的复杂度状态的数量，这是 0（NM * 2 ^（分（N，M））），对不起，我忘了一个额外的因素，我的评论。

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.