问满足特定条件的子格网计数

EN

您需要一种避免重复项的方法；例如，您可以使用x0,y0,x1,y1标识一个矩形。

open, valid = empty sets of rectangles
add all red squares to a set `open`
while not `open` empty,
    take the first `open` rectangle
    for each direction, 
       try to grow it 1 square in that direction
          if growth possible (not outside matrix, not blue), 
              and result not in `valid` or `open`, 
                  add to `open`
    add it to `valid`

valid的大小是您查找的计数。可能会更优化，但至少它看起来是正确的，并且应该比查找所有可能的矩形快得多，因为a)如果没有红色，它永远看不到矩形；b)一旦矩形包含蓝色，它就永远不会继续查找。

在大小为n的网格上的“查看所有可能的矩形”算法将必须查看~n^4矩形(在信封的后面，因为有n^2 x0,y0 pairs和n^2 x1,y1 pairs)；并且，对于每个矩形，检查是否有蓝色和红色(因此，O(n^5)是一个低球估计；O(n^6)可能更接近标记)。重要的是，无论红色和蓝色的分布如何，它都会有这样的成本。我的建议在有效结果较少的情况下具有更好的复杂性:如果没有红色，或者如果它们都被蓝色(棋盘图案)包围，则为O(n^2)。在最坏的情况下，它的复杂度也较低，因为它只有在有效时才会增长--可能在定义为全red的O(n^4)最坏情况下增长。