计算2D网格中的帧

Question

给出了一个由0和1s组成的[NxM]矩阵。在这个矩阵中找出没有1s (每个单元格为0)的方框数。固定正方形的框架是一组单元格，每个单元格都是最左、最右、最上或最底层的单元格之一。因此，边长1的方框包含1单元，侧长2包含4，边长3-8单元，侧长4- 12单元。

大小为4的示例框架是：

0000
0  0
0  0
0000

我们需要计算只由0组成的平方帧的数目。

示例将N=3和M=4以及矩阵设为：

0100
0100
0000

那么答案是12，因为有10个大小的帧和2个大小的帧。

主要问题是N，M可以上- 1 ≤ N，M ≤ 2000。因此，需要O(N^2)方法。

Answer 1

每一帧都可以等同于一对矩阵的元素--相反的角。假设左上角和右下。它们必须在对角线上，很明显。首先要注意的是，如果是的话。((1;1);(5;5))是我们的框架，元素(1;1)和(5;5)必须为null。此外，从(1;1)向右和向下至少有四个空。从(5;5)到左边和上面的位置相同。因此，第一个想法是计算每一个元素x的最小零，与自己向下，右和左向上(线性时间)。

如果我没有犯错误，那就是一个例子：

-->(x;y) = (min(right, down); min(left,upward))

00000    (5;1)(1;1)(1;1)(2;1)(1;1)
01101    (1;1)(0;0)(0;0)(1;1)(0;0)
01001--->(1;1)(0;0)(2;1)(1;2)(0;0)
00000    (2;1)(1;1)(1;2)(1;4)(1;1)
01110    (1;1)(0;0)(0;0)(0;0)(1;1)

第二个想法:分别分析每条对角线，从左上角到右下角.

1. (1;1)
2. (2;1)(0;0)
3. (1;1)(1;1)(0;0)
4. 等等..。

对于对，需要一些结构Q，这将允许您：

• 删除元素的后继小于..。O(lg n)
• 前驱体大于..。O(lg n)
• 加对。O(lg n)

将全局结果设置为null。每条对角线的算法都很简单。取空Q，迭代以下元素，i = 0,1,2,...。每一项：

• 从Q元素中擦除，其中后继值小于i。(它只能是最小的继承者的元素。)
• 如果实际元素不是(0;0)：
  • 推送对、前驱：i和后继:最后一个元素的个数与实际元素可以配对。它是i+x_i-1，其中x_i是实际元素的min(right, down)。
  • Q中前驱体大于i-y_i的计数元素。这些是可以与实际元素配对的元素。将该数字添加到“全局”结果中。

​

在全局结果中，你得到了答案。这是O(NM )算法，我不确定，你是否能做得更快。

例如对角线。我们要分析table=(5；1)，(0;0)，(2;1)，(1;4)，(1；1)。

Generally for element:
   Current element: (x;y); i=i           // O(1)
   Q.erase_smaller_than(i)              // O(lg N)
   if (x;y) == (0;0) :                  // O(1)
        skip element
   Q.emplace(i, i+x-1)                  // O(lg N)
   result += Q.count_bigger_than(i-y)   // O(lg N)


For diagonal example:

0. Q = {}
   result = 0
   for element in ((5;1),(0;0),(2;1),(1;4),(1;1))

1. Current element: (5;1); i = 0
   Q.erase_smaller_than(i)
   Q.emplace(i, i+5-1) // (0; 4)
   temp = Q.count_bigger(i-1) //taking only predecessor
   // bigger than -1, 1. element (frame with only one element)
   result += temp // result = 1

2. Current element: (0;0); i = 1
   Q.erase_smaller_than(i) //nothing changed
   (0;0) element, skip

3. Current element: (2;1); i = 2
   Q.erase_smaller_than(i) //nothing changed, Q = {(0;4)}
   Q.emplace(i, i+2-1) // (2;4)
   temp = Q.count_bigger(i-1) // only current element
   result += temp // result = 2

4. Current element (1;4); i = 3
   Q.erase_smaller_than(i) //Q = {(0;4)(2;4)}
   Q.emplace(i; i+1-1) // (3; 3)
   temp = Q.count_bigger(i-4) //all three elements from Q
   result += temp // result = 5\

5. Current element (1;1); i = 4
   Q.erase_smaller_than(i) // Q = {}
   Q.emplace(i;i+1-1) // (4;4)
   temp = Q.count_bigger(i-1) // only current element
   result += 1

6. End of loop. Print "On main diagonal $result frames have corners.".
   Continue that algorithm for next diagonal lines.

Answer 2

我用c#中的代码解释我的算法：

static void Main(string[] args)
{
    int[,] ar = new int[,] { {0,1,0,0}, 
                             {0,1,0,0}, 
                             {0,0,0,0} };

    int count = 0; // Count of square matrices
    int sum = 0;   // A temporary variable for checking validation of a square matrices

    int max = 0;   // Max size of square matrices for each point

    for (int i = 0; i < ar.GetLength(0) ; i++)
    {
        for (int j = 0; j < ar.GetLength(1); j++)
        {
            if (ar[i, j] == 0)
            {
                //calculate maximum size of square Matrices
                max = ar.GetLength(0) - i;
                if (max > ar.GetLength(1) - j)
                    max = ar.GetLength(1) - j;

                //Search kxk square matrice
                for (int k = 0; k < max; k++)
                {
                    sum = 0;
                    // Search Borders
                    for (int l = 1; l <= k; l++)
                    {
                        sum += ar[i + l, j];
                        sum += ar[i, j + l];
                        sum += ar[i + l, j + k];
                        sum += ar[i + k, j + l];
                        if (sum > 0)
                            break;
                    }
                    sum += ar[i + k, j + k];

                    if (sum == 0)
                        count++;
                }
            }
        }
    }

    Console.WriteLine("{0}", count.ToString());
    Console.ReadKey();
}

我使用一个sum变量来找到它，所有的边界点都是0。

Answer 3

一个框架总是有一个左上方的0。因此，您可以遍历矩阵(对于N和M内部)，在每次迭代中，计算左上角元素为0的所有帧。在你的例子中：

0100
0100
0000

1. 对于N=1和M=1，您可以找到1框架。
2. 接下来是N=1和M=2。你可以找到0框架。
3. 对于N=1和M=3，您可以找到2。

等等..。