Explaining "counting the number of subgrids" solution in the Competitive Programming Guide Book

Question

I've come across the explanation for a problem in the competitive programmer's handbook and don't really understand how it encompasses all the solutions for the problem and I was wondering if anyone could explain it for me. I'm not sure if I'm just not understand the solution correctly if if I'm missing something about the problem. An image of the question and solution are below:

From the way I understand it, the question is simply asking for subgrids (four corners that make an a x b or a x a box) where each corner is black. Their solution (from what I understand) is that you count the number of black box pairs in each column then calculate the total by using the formula count(count-1)/2. My question if I'm understand this correctly is how does this encompass all the cases? The particular example I had in my head was this:

X O O O O O
O X O O O O
O O X O O O
X O O O O O 
O X O O O O
O O X O O O

and

X X X O O O
O O O O O O
O O O O O O
X X X O O O 
O O O O O O
O O O O O O

Wouldn't these two boxes give the same answer using the solution provided? You would get count = 3 for both inputs which would output 3 for the total for each input, despite them having different solutions. I just feel like I'm missing something when it comes to the solution.

Thank you for your help.

Answer 1

The algorithm given as pseudo code is only the inner loop, as it were. The outer loop is, as explained in the preceding text, a loop over all pairs of rows.

int count_subgrids(const int** color, int n)
{
    int subgrids = 0;
    for(int a=0; a<n; ++a)
        for(int b=a+1; b<n; ++b) {    // loop over pairs (a,b) of rows 
            int count=0;
            for(int i=0; i<n; ++i) {  // loop over all columns
                if(color[a][i]==1 && color[b][i]==1)
                    ++count;
            }
            subgrids += ((count-1)*count)/2;
        }
    return subgrids;
}

In your first example, count=0 for any pair of rows, so subgrid remains 0 too. In your second example, there are three pairs of rows, namely (a,b)=(0,1), (0,2), and (1,2) for which count=2, such that subgrid=3 in the end.