一、题目信息
二、解题思路
-
1、这里采用 C++ 解答，题目限制如下
-
2、输出要求？
-
根据输出可以看出第一行输出的是所有1*1子矩阵中符合完美矩阵（矩阵中 0 的个数等于 1 的个数）条件的矩阵个数，其余输出同理。
-
3、如何遍历所有矩阵
-
采用按行遍历的方式。比如>采用按行遍历的方式。比如 2*2 的矩阵，从左上角2*2的矩阵开始，往右移动一个单位即得到一个新的矩形，直至移动到 200 * 200 矩阵的最后一列。接下来还从最左边开始（左上角的矩阵向下移动一行），同理再每向右移动一个单位得到一个新矩阵。整个过程即从左上角2*2的矩阵开始，移动到右下角2*2的矩阵结束，得到了所有的子矩阵。
-
4、如何判断子矩阵是否为完美矩阵？
-
计算矩阵的值（所有元素的和），值=矩阵元素个数/2(必须整除)即完美矩阵，首先对 2 取模，模不为零不满足，因为不能整除
-
5、如何快速计算矩阵的值
-
首先保存前一个矩阵（旧矩阵）的值，每移动一个单位不用遍历新矩阵的所有元素来计算值，计算新矩阵相较于旧矩阵新增列与失去列的差值即可，差值与旧矩阵值的和就得到了新矩阵的值
点击查看代码
#include <iostream>
#include<array>
void checkPerfectMatrix(const size_t childLine, const size_t& maxLine, const std::array<std::array<char, 200>, 200>& matrix, size_t& perfectMatrix) {
// 奇数个矩阵元素不符合要求
if (childLine * childLine % 2) {
return;
}
size_t sum = 0, curHeadOfRowMatrixValue = 0, matrixRowStart = 0, matrixRowEnd = childLine, matrixColumnStart = 0, matrixColumnEnd = childLine;
// child matrix
for (int i = matrixRowStart; i < matrixRowEnd; i++) {
for (int j = matrixColumnStart; j < matrixColumnEnd; j++) {
sum += matrix[i][j] - '0';
}
}
curHeadOfRowMatrixValue = sum;
while(1) {
// sum of matrix elem
if (matrixColumnStart > 0) {
for (int i = matrixRowStart; i < matrixRowEnd; i++) {
sum += (matrix[i][matrixColumnEnd -1] - matrix[i][matrixColumnStart - 1]);
}
}
// judge perfect matrix
if ((sum != 0) && (sum == childLine*childLine/2)) {
perfectMatrix++;
}
// reinit
matrixColumnStart++; matrixColumnEnd++;
if (matrixColumnEnd > maxLine) {
matrixRowStart++, matrixRowEnd++, matrixColumnStart = 0, matrixColumnEnd = childLine;
for (int i = 0; i < childLine; i++) {
sum = curHeadOfRowMatrixValue;
sum += (matrix[matrixRowEnd - 1][i] - matrix[matrixRowStart - 1][i]);
curHeadOfRowMatrixValue = sum;
}
if (matrixRowEnd > maxLine) {
break;
}
}
}
}
int main() {
size_t maxLine = 0, perfectMatrix = 0; const size_t LINE = 0; const size_t ROW = 1;
std::array<std::array<char, 200>, 200> matrix;
std::cin >> maxLine;
// init matrix
for (int i = 0; i < maxLine; i++) {
for (int j = 0; j < maxLine; j++) {
std::cin >> matrix[i][j];
}
}
for (int i = 0; i < maxLine; i++) {
// output perfect matrix
checkPerfectMatrix(i+1, maxLine, matrix, perfectMatrix);
std::cout << perfectMatrix << std::endl;
perfectMatrix = 0;
}
return 0;
}
-
6、结果
