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

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”个红色片断，并且绿色块的数量最大。

我的问题：

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

一些直觉：

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

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

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

情况1例如：

情况2：

另一个深入的直觉：

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

1. 然后，我们首先创建覆盖壁橱的两个红色点的矩形。（例如，我们的矩形将扩展到y = 3，x = 2）覆盖了所有区域。

2. 然后我们检查红色点的壁橱y轴是什么，该轴大于当前矩形的y（y = 3），红色点的壁橱x轴是什么，它大于当前矩形的x（即x = 2），壁橱x和y也可以来自相同的第三个红点，而不必来自两个不同的红点。

3. 这样，我们可以看到可以扩展矩形的“距离”。

4. 然后，在步骤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)，编程方法如下：

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

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

UPDATE：现在有一个示例执行

一个示例，在每个单元格中分别(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元的总和。