python - 棋盘游戏:找到带有限制的红点的最大绿点

Question

场景：


在大小为MxN的棋盘上，有红色和绿色的棋子。
板上的每个正方形可以包含任意数量的任何颜色的块。 （我们可以在同一正方形中有5个-3个绿色和2个红色，例如绿色，绿色，红色，红色或其他数字）
我正在寻找板上的轴对齐矩形，其中包含尽可能多的绿色块。
但是，矩形不能包含超过给定数量的红色块。
矩形的一个角必须为（0,0）。


例：

电路板尺寸为6x4，红色部分标记为“ x”，绿色部分标记为“ o”。

+-+-+-+-+-+-+
3 | | | | o | x | o |
+-+-+-+-+-+-+
2 | o | | x | | | o |
+-+-+-+-+-+-+
1 | o | | o | | o | x |
+-+-+-+-+-+-+
0 | | o | | x | | x |
+-+-+-+-+-+-+
0 1 2 3 4 5



如果我们允许2个红色块，那么（4,2）是一个最佳解决方案，因为（0,0）和（4,2）之间的区域包含5个绿色块和2个红色块。
最多有2个红色块的点最多包含5个绿色块。 （3,3）也是一个最佳解决方案。
如果我们允许3个红色小块，那么（4,3）是唯一的最佳解决方案，有6个绿色小块。


我得到：


板子尺寸
所有绿色和红色部分的坐标，
允许的红色块数（“ maxRed”）


目标：
对于任何给定的“ maxRed”，该类应能够计算坐标（x，y），以使（0,0）和（x，y）之间的轴对齐矩形最多包含“ maxRed”个红色片断，并且绿色块的数量最大。

我的问题：

通过遍历具有最大绿色点和给定最大红色点的所有可能的矩阵（以找到最大的三角形）来解决此问题显然是无效的，我正在尝试找到一种无需使用蛮力就能找到该矩阵的方法。

一些直觉：

我想查看从原点(0,0)允许在矩形中的壁橱最大红色点（如果maxRed = 2，则最接近两个红色点），然后从中检查矩形的所有可能的“扩展”点（只是宽度，只是高度，宽度和高度，等等。）我也认为效率不高（在最坏的情况下效率很低）。

然后我想如果maxRed等于2并找到最接近的两个红色点，那么我们可以检查第三个maxRed（如果不存在，则将整个矩阵作为矩形返回），然后以某种方式搜索“小于”选项的数量-仍然需要考虑所有情况（第三个点可以在当前矩形的顶部，或者从它的左侧，或者对角线），以及是否来自例如在它的顶部，那么可能会有一个情况，我可以将其宽度扩展-也许不能（因为它的右边还有另一个红点）。但是您知道了，以某种方式找到了一种并非蛮力且尽可能高效的算法。

问题2：我还想知道如何处理另一个有趣的问题：
如果坐标定义为“浮动”，这意味着该板没有网格，您将如何解决该问题。现在，您需要返回最佳浮点（x，y）坐标，以使（0,0）和（x，y）之间的区域最多包含“ maxRed”红色块，而绿色块的数目最大。您将如何找到它，复杂性如何？

案例1，例如：


情况2：


另一个深入的直觉：

边缘情况：如果地图中的红点小于2，则返回所有矩阵的矩形。


然后，我们开始创建覆盖壁橱的两个红色点的矩形。 （例如，我们的矩形将扩展到y = 3，x = 2）覆盖所有区域。
然后我们检查红色点的壁橱y轴是什么，它比当前矩形的y大（y = 3），红色点的壁橱x轴是什么，它大于当前矩形的x（即x = 2），壁橱x和y也可以来自相同的第三个红点，而不必来自两个不同的红点。
这样，我们可以看到可以扩展矩形的“距离”。
然后，在步骤3中，如果可能，我们将尝试迭代上移（i + 1），并检查j的所有扩展，然后转到i + 2并检查所有j。


4.1，然后尽可能右移（j + 1），并检查所有i，然后继续进行j + 2，依此类推。

并返回我们可以构建的最高矩形-并且在此过程中，我们不会检查太多的i和j。

但这还不够

因为在“案例2”中有一个边缘案例

在同一地点有2个红点，因此我们将必须仔细检查第二最远的红点（如果x或y或两者都比第一个壁橱的红点明显更远）是否还有另一个红点在其中，如果同一单元格中总共有两个红点，则我们将其扩展到x或y-并从那里继续向上/向下扩展。

（我们可以看到它是对角线，还是从右边或从顶部看），如果它是从第一个红点的右边（意味着x大于我们当前的x-仅在x轴上），那么我们可以检查多远我们可以扩展顶部-通过查看红色点列表（如果我们在顶部有红色点），如果没有，那么我们将立即扩展到结尾，如果第二个红色点在我们顶部，则可以通过相同的方法进行检查向右延伸多远。

如果第二个红点在我们的对角线上（如用法示例中所示），则我们检查仅可以向左延伸多远，以及仅可以向顶部延伸多远，然后看看对我们有什么好处寻找更多的绿点。

我猜这个解决方案应该可以工作，并给出O（1）我猜想的时间复杂度。

Answer 1

如果您认为只有两个整数变量i，j和0 <= i <= M, 0 <= j <= N，则可以使用动态编程来解决。我将尝试在没有LaTeX引擎的情况下清楚地编写此内容，请耐心等待。

假设您创建了四个M * N整数G，R，V和L矩阵。对于每个点(i, j)，g_ij表示该正方形上的绿色块数，而r_ij表示红色块的数目。 v_ij表示矩形(0, 0) - (i, j)中的绿色块数，如果红色块的数量过多，则为0，l_ij表示矩形中的红色块数，如果原始值正在变化，则为无穷大超过限制。如果我谈论一个单元格的值，我的意思是v_ij，则一个单元格的限制等于l_ij。

从(0, 0)点开始，编程方法如下：


给定点(i, j)
可能的指示方向为(i + 1, j)，右侧为(i, j + 1)。
对于(i + i, j)，矩形l_(i + 1)j中的红色块数等于前一个单元格l_ij的限制+矩形上方行中的红色块数，因此单元格(0, j)至(i + 1, j)。如果使用限制l_ij，则不必为一个步骤计算(i + 1) * j单元格的总和，而只需计算行中j + 1单元格-j单元格的总和再加上一个存储的值。计算v_(i + 1)j时也是如此，只需使用存储值v_ij加上上一行中的绿色块数即可。
如果超过了红色块的限制数量，则可以在(i + 1, j)和右上角(M, N)之间创建一个矩形，并将所有这些单元格的限制指定为超出-因为在那里可以形成的所有可能的矩形必须包含矩形(0, 0) - (i + 1, j)，因此它们必须包含太多红色块。正确的计算非常相似。
一旦不再有未知的片段，只需找到O（MN）时间中V的最大值即可。


对于您的第二个问题，可能的近似值是在0到1之间采用步长大小，然后将所有值除以该步长，然后向下舍入，因此步长为1/10的(2/3, 7/5)将变为(6, 14)。然后使用这些步骤应用算法。您可以多次运行，减小步长，在两次运行之间存储和转换矩阵V，因此可以避免进行大量计算。希望对您有所帮助！

更新：现在有一个示例执行

在每个单元格中的示例(x, y)分别表示绿色和红色的块数。矩阵G和R旁边是-空值表示0。
红色棋子的数量限制为3。

                                       G                   R
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
3 |(1,2)|     |     |(4,0)|  3 | 1 |   |   | 4 | 3 | 2 |   |   |   | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
2 |     |(3,1)|     |(1,2)|  2 |   | 3 |   | 1 | 2 |   | 1 |   | 2 | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
1 |(1,1)|(1,1)|     |     |  1 | 1 | 1 |   |   | 1 | 1 | 1 |   |   | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
0 |     |(0,1)|(3,1)|(1,1)|  0 |   |   | 3 | 1 | 0 |   | 1 | 1 | 1 | 
  +-----+-----+-----+-----+    +---+---+---+---+   +---+---+---+---+ 
     0     1     2     3         0   1   2   3       0   1   2   3   

从(0, 0)开始，我们有0个红色块和0个绿色块，因此V和L如下所示：

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 |   |   |   |   | 3 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
2 |   |   |   |   | 2 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
1 |   |   |   |   | 1 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 |   |   |   | 0 | 0 |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

为了完整性，我确实在V和L中填充零值。
现在我们可以上升到(1, 0)，然后上升到(0, 1)。向上，我们得到l_10 = l_00 + r_10 = 0 + 1 = 1和v_10 = v_00 + g_10 = 0 + 1 = 1。在右边，我们得到l_01 = l_00 + r_01 = 0 + 1 = 1和v_01 = v_00 + g_01 = 0。这给我们以下情况：

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 |   |   |   |   | 3 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
2 |   |   |   |   | 2 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
1 | 1 |   |   |   | 1 | 1 |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 | 0 |   |   | 0 | 0 | 1 |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

现在，我们可以从(1, 0)上升，直接从(1, 0)上升，这等效于从(0, 1)上升，我们可以从(0, 1)上升。
如果从(1, 0)升至(2, 0)，则会得到l_20 = l_10 + r_20 = 1 + 0 = 1和v_20 = v_10 + g_20 = 1 + 0 = 1。如果从(1, 0)转到(1, 1)，则得到l_11 = l_10 + r_01 + r_11 = 1 + 1 + 1 = 3。请注意，这与从(0, 1)升至l_11 = l_01 + r_10 + r_11 = 1 + 1 + 1 = 3完全相同。类似地，v_11 = v_10 + g_01 + g_11 = 1 + 1 = 2。最后，如果我们从(0, 1)转到(0, 2)，则得到l_02 = l_01 + r_02 = 1 + 1 = 2和v_02 = v_01 + g_02 = 0 + 3 = 3。这将导致以下模式：

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 |   |   |   |   | 3 |   |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
2 | 1 |   |   |   | 2 | 1 |   |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
1 | 1 | 2 |   |   | 1 | 1 | 3 |   |   | 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 | 0 | 3 |   | 0 | 0 | 1 | 2 |   | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

现在，我们可以从(2, 0)上升，从(2, 0)上升，这等效于从(1, 1)上升，从(1, 1)上升，这等效于从(0, 2)上升，或者从(0, 2)上升。如果从(2, 0)升至(3, 0)，则会得到l_30 = l_20 + r_30 = 1 + 2 = 3和v_30 = v_20 + g_30 = 1 + 1 = 2。
我们可以通过从(2, 1)向上计算来计算(2, 0)，但是从(1, 1)向上可以允许我们对更大一部分预先计算的矩形（4个单元格而不是3个单元格）进行相同的计算。我们得到l_21 = l_11 + r_20 + r_21 = 3 + 0 + 1 = 4。由于超出了限制，因此v_21 = 0。现在，任何包含(2, 1)的矩形将具有与(2, 1)完全相同的单元格，包括那些加起来最多为4个红色部分的单元格。因此，所有包含(2, 1)的矩形都必须无效。这些都是带有x >= 2和y >=1的单元格。为了明确起见，我们给它们l_xy = Inf。
单元格(1, 2)包含(0, 0)，但是由于l_12 = l_11 + r_02 + r_12 = 3 + 1 + 0 = 4，该单元格无效，(1, 3)遵循与上述相同的逻辑。

最后，如果我们从(0, 2)转到(0, 3)，则得到l_03 = l_02 + r_03 = 2 + 1 = 3和v_03 = v_02 + g_03 = 3 + 1 = 4。这将导致以下模式：

          V                   L         
  +---+---+---+---+   +---+---+---+---+ 
3 | 2 | 0 | 0 | 0 | 3 | 3 |Inf|Inf|Inf| 
  +---+---+---+---+   +---+---+---+---+ 
2 | 1 | 0 | 0 | 0 | 2 | 1 |Inf|Inf|Inf| 
  +---+---+---+---+   +---+---+---+---+ 
1 | 1 | 2 | 0 | 0 | 1 | 1 | 3 |Inf|Inf| 
  +---+---+---+---+   +---+---+---+---+ 
0 | 0 | 0 | 3 | 4 | 0 | 0 | 1 | 2 | 3 | 
  +---+---+---+---+   +---+---+---+---+ 
    0   1   2   3       0   1   2   3    

如您所见，具有最高值的矩形是由点(0, 3)具有值4形成的矩形，我们在计算16个像元中只有10个时发现了这一点。当然，该算法的上限是O(MN)，但是实际上这是不可避免的，因为考虑没有红色碎片或限制很高的情况。然后，您仍然必须计算所有M * N单元格的总和。