Count frames in a 2D grid

Question

Given a [NxM] matrix consisting of 0s and 1s. Find the number of square frames with no 1s (each cell is 0) in this matrix. A frame of a fixed square is a group of cells each of them is one of the leftmost, rightmost, topmost or bottommost cells. Thus a square frame with the side length 1 contains 1 cell, with the side length 2 contains 4, with the side length 3 - 8 cells, with the side length 4 - 12 cells.

Example frame of size 4 is :

0000
0  0
0  0
0000

We need to count the number of square frames consisting only of 0s.

Example Let N=3 and M=4 and matrix be :

0100
0100
0000

Then answer is 12 as there are 10 one sized frames and 2 two sized frames.

Main problem is N,M can be up-to 1 ≤ N, M ≤ 2000 . So O(N^2) approach is required.

Answer 1

Each frame can be equated with pair of matrix's elements - opposite corners. Assume top left and right down. They have to be on same diagonally line, obvious. Firstly notice that if for eg. ((1;1);(5;5)) is our frame, elements (1;1) and (5;5) have to be null. Furthermore, to the right and down from (1;1) are at least four nulls. Same to the left and upward from (5;5). So, the first idea is count for each element x minimum of nulls down-right and left-upward with himself (linear time).

If I didn't make mistake, it's example:

-->(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)

Second idea: analyse each diagonally line separately, from up-left corner to down-right.

1. (1;1)
2. (2;1)(0;0)
3. (1;1)(1;1)(0;0)
4. And so on...

You need some structure Q for pairs, which will allow you to:

• Erase elements with successor smaller than... O(lg n)
• Count elements with predecessor bigger than... O(lg n)
• Add pair. O(lg n)

Set global result as null. Algorithm for each diagonally line is easy. Take empty Q. Iterate the following element, i = 0,1,2,.... For each:

• Erase from Q elements, in which successor is smaller than i. (It could be only element with the smallest successor.)
• If actual element isn't (0;0):
  • Push pair, predecessor: i, and successor: number of last element with witch actual element can pairs up. It's i+x_i-1, where x_i is min(right, down) of actual element.
  • Count element with bigger predecessor in Q than i-y_i. These are the elements that can be paired wits actual element. Add that number to 'global' result.

In global result, you have the answer. It's O(NM log N) algorithm, I'm not sure, if you can do it faster.

---

Example for diagonal. We have table=((5;1),(0;0),(2;1),(1;4),(1;1)) to analyse.

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.