c++ - 在《竞争编程指南》中解释 “counting the number of subgrids”解决方案

Question

我已经在竞争性程序员手册中找到了关于问题的解释，但我并不真正理解它如何包含问题的所有解决方案，我想知道是否有人可以为我解释它。如果不确定有关该问题的信息，我不确定是否只是无法正确理解解决方案。问题和解决方案的图片如下:



从我的理解来看，问题是简单地询问每个角都是黑色的子网格(四个角组成a x b或x a a box)。他们的解决方案(据我了解)是，您计算每列中的黑盒对数，然后使用公式count(count-1)/ 2计算总数。我的问题是，如果我对问题的理解正确，那么这将如何涵盖所有情况？我脑子里有一个特别的例子是:

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

和

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

使用提供的解决方案，这两个盒子不会给出相同的答案吗？尽管两个输入都有不同的解决方案，但两个输入都将得到count = 3，这将为每个输入总计输出3。我只是觉得我在解决方案方面缺少什么。

谢谢您的帮助。

Answer 1

照原样，伪代码给出的算法只是内部循环。如前文所述，外部循环是所有所有行对之间的循环。

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;
}

在您的第一个示例中，一对任何行都为 count=0，因此 subgrid仍为 0。在您的第二个示例中，有三对行，即 (a,b) = (0,1)， (0,2)和 (1,2)，其中 count=2最终为 subgrid=3。