There's this really good article on how to find the maximal empty subgrid of a grid so one might wonder, "How do we find the number of empty subgrids of a grid?" I first saw the answer to the second question in this solution to CHSGMNTS on CodeChef by lohit_97 (found on CodeChef and on CodeForces), so thanks to them for the following algorithm!

First, here is a more formalized way of saying the problem:

• The first line of input contains two integers width and height (where 1 ≤ width, height ≤ 1000).
• The next height lines of input contain width integers that fit into long in C/C++.
• Let matrix[i][j] be the integer number i on row number j.
• Find the number of tuples (a, b, c, d) such that matrix[i][j] is 0 for all a ≤ i ≤ c and b ≤ j ≤ d.

The way we can solve this problem is by keeping an array emptyToLeft[i][j] which is the maximum number such that i - emptyToLeft[i][j] < x ≤ i implies matrix[x][j] is 0. (If matrix[i][j] is not 0, then we just set emptyToLeft[i][j] to 0 to make the inequality always false.)

Once we have that, we loop through each column i and in each column, we make a stack and a tempAnswer = 0. In the bottom of a stack, we start with  - 1 and as we loop through each row j, each row is popped on and some rows are popped off in order to preserve the property that between two consecutive stack elements a and b where b is directly above a, we have a < y ≤ b implies emptyToLeft[i][y] ≥ emptyToLeft[i][b]. By the definition of emptyToLeft, this means i - emptyToLeft[i][b] < x ≤ i and a < y ≤ b implies matrix[x][y] is 0. Thus, all such (x, y) as (a, b) and (i, j) as (c, d) in the tuple (a, b, c, d) is an answer. Therefore, two consecutive stack elements a and b give us (b - a) * emptyToLeft[i][b] answers, so we add that to tempAnswer when we add b to the stack and subtract that from tempAnswer when we pop b off. Finally, the answer is simply the sum of all tempAnswers across all i, j.

Here is the C code for this algorithm:

#include <stdio.h>
#include <stdlib.h>
#define REPEAT(token, num) for (token = 0; token < num; token++)

typedef long num_cells;
typedef long cell;
typedef long long num_matrices;

cell matrix[1000][1000];
num_cells width, height, emptyToLeft[1000][1000], stack[1000], stackLength;
num_matrices answer, tempAnswer;

int main() {
    num_cells i, j, prevToLeft;
    //Get the input for the matrix:
    scanf("%li %li", &width, &height);
    REPEAT(j, height) REPEAT(i, width) scanf("%li", matrix[i]+j);

    //Create emptyToLeft by looping through the rows:
    REPEAT(j, height) {
        //This is the previous emptyToLeft, which starts out at 0 because at the beginning of a row, there are no elements to the left.
        prevToLeft = 0;
        //Loop through each column:
        REPEAT(i, width) {
            //If matrix[i][j] != 0, then emptyToLeft[i][j] = 0.
            if (matrix[i][j]) emptyToLeft[i][j] = 0;
            //Otherwise, add one to prevToLeft.
            else emptyToLeft[i][j] = prevToLeft+1;
            //Also, update prevToLeft:
            prevToLeft = emptyToLeft[i][j];
        }
    }

    REPEAT(i, width) {
        //For each column, create a stack with -1 at the bottom.
        stack[0] = -1, stackLength = 1;
        //Also, reset tempAnswer:
        tempAnswer = 0;
        //Loop through each row:
        REPEAT(j, height) {
            //If emptyToLeft[i][stack[stackLength-1]] >= emptyToLeft[i][j], then putting j onto the stack will violate the stack property, so we need to pop the stack:
            while (stack[stackLength-1] != -1 && emptyToLeft[i][stack[stackLength-1]] >= emptyToLeft[i][j]) {
                //Update tempAnswer now that we are going to pop the stack:
                //Note that here, stack[stackLength-1] is described as b above while stack[stackLength-2] is a.
                tempAnswer -= (stack[stackLength-1]-stack[stackLength-2])*emptyToLeft[i][stack[stackLength-1]];
                //Pop the stack:
                stackLength--;
            }
            //Add the current row to the stack and update tempAnswer accordingly.
            stack[stackLength++] = j;
            tempAnswer += (stack[stackLength-1]-stack[stackLength-2])*emptyToLeft[i][stack[stackLength-1]];
            //Finally, add tempAnswer to answer across all i, j.
            answer += tempAnswer;
        }
    }
    //Print the answer:
    printf("%lli\n", answer);
    
    exit(0);
}

Notice that we have a while loop inside of the j loop, giving us a third inner loop and thus possibly O(height²width) complexity. However, each run of the while loop pops an element off the stack and we only add an element to the stack for each j, meaning overall, for one i, we can do at most height pops. Thus, the j loop is O(height) for each i and the while loop is O(height) for each i, which gives us O(height·width) complexity for this problem.