划分二维矩阵

我想你只能做一个水平切割或垂直切割。

一种方法 “一个矩阵” 是:(你需要重复地把这个应用到你得到的每个分区上)。

计算每行中的个数和每列中的个数,将它们存储在两个数组中,如

OnesInRow[num_rows] , OnesInColumn[num_cols]

还要计算矩阵中1的总数,实际上是上述任意一个数组中所有元素的值之和。

total = Sum( All elements in OnesInRow )

例如,您可以像 OnesInRow[1] (假定行索引从0开始)。同样,第3列中的个数是 OnesInCol[2] .

现在考虑这样的水平切割:

0,0,0,0,0

0,0,1,0,0

0,0,0,1,0

0,0,0,0,0

您在每个分区中获得的数量是: OnesInRow[0], Total - OnesInRow[0]

为此:

0,0,0,0,0

0,0,1,0,0

0,0,0,1,0

0,0,0,0,0

它是: Total - ( OnesInRow[0] + OnesInRow[1] ) , OnesInRow[0] + OnesInRow[1]

为此:

0,0,0,0,0

0,0,1,0,0

0,0,0,1,0

0,0,0,0,0

它是: Total - (OnesInCol[0] + OnesInCol[1] ), OnesInCol[0] + OnesInCol[1]

所以你只需要考虑所有的行切割和列切割,并考虑哪一个切割将导致两个相等的分区。

int count = 0;
int prevOnes = 0;
int onesInRowAboveThisCut = 0;
for ( int i = 1; i < rows; i++ ) {
   onesInRowAboveThisCut = prevOnes + OnesInRow[i-1];
   if ( onesInRowAboveThisCut= total/2 ) count++;
   prevOnes = onesInRowAboveThisCut;
}
prevOnes = 0;
int onesInColBeforeThisCut = 0;
for ( int i = 1; i < cols; i++ ) {
   onesInColBeforeThisCut  = prevOnes + OnesInCol[i-1];
   if ( onesInColBeforeThisCut = total/2 ) count++;
   prevOnes = onesInColBeforeThisCut ;
}

return count;

然后,对于从这样一个分区得到的每个矩阵,您可以递归地重复这个过程,直到您不能剪切,即数组中只有一个元素。 在每次递归中,都要维护一个计数变量并更新它。