寻找回忆碎片：计算矩阵中正方形的数量

题目描述

白姬身处一个充满回忆碎片的世界，她试图在一个 01 矩阵中寻找排成正方形的四个残片，以找回自己的记忆。

给定一个大小为 n x n 的 01 矩阵 A=(a_ij)_n×n，其中 a_ij = 1 表示矩阵中 (i, j) 位置存在碎片。

你的任务是找出所有由四个碎片构成的正方形，正方形可以是斜的。

注意：

四个点不可重合。* 只要是相同的四个点，无论怎么排列都视为相同的点集。

输入格式

第一行包含两个整数 n 和 o，其中 n 表示矩阵的大小，o 用于指示更多特殊性质（在本题解中不考虑 o）。* 接下来 n 行，每行包含一个长度为 n 的 01 字符串，表示矩阵的每一行。

输出格式

输出一个整数，表示矩阵中正方形的数量。

样例

输入

4 01111111111111101

输出

解题思路

我们可以遍历矩阵中的每一个点，并将每个点视为潜在的正方形的左上角顶点。然后，我们可以检查以该点为左上角顶点的四个方向上是否存在构成正方形的另外三个顶点。

为了优化算法，我们可以预先计算每个点在各个方向上连续 '1' 的数量。这样，我们就可以在 O(1) 的时间内判断是否存在构成正方形的顶点。

C++ 代码cpp#include #include

using namespace std;

int main() { int n, o; cin >> n >> o;

vector<vector<int>> matrix(n, vector<int>(n, 0));    for (int i = 0; i < n; i++) {        string row;        cin >> row;        for (int j = 0; j < n; j++) {            matrix[i][j] = row[j] - '0';        }    }

int count = 0;

// 遍历矩阵中的每个点    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            if (matrix[i][j] == 1) {                // 在当前点的右下方找到一个点                if (i + 1 < n && j + 1 < n && matrix[i + 1][j] == 1 && matrix[i][j + 1] == 1 &&                    matrix[i + 1][j + 1] == 1) {                    count++;                }                // 在当前点的左下方找到一个点                if (i + 1 < n && j - 1 >= 0 && matrix[i + 1][j] == 1 && matrix[i][j - 1] == 1 &&                    matrix[i + 1][j - 1] == 1) {                    count++;                }                // 在当前点的右上方找到一个点                if (i - 1 >= 0 && j + 1 < n && matrix[i - 1][j] == 1 && matrix[i][j + 1] == 1 &&                    matrix[i - 1][j + 1] == 1) {                    count++;                }                // 在当前点的左上方找到一个点                if (i - 1 >= 0 && j - 1 >= 0 && matrix[i - 1][j] == 1 && matrix[i][j - 1] == 1 &&                    matrix[i - 1][j - 1] == 1) {                    count++;                }            }        }    }

cout << count << endl;

return 0;}

复杂度分析

时间复杂度：O(n^2)，其中 n 是矩阵的边长。* 空间复杂度：O(1)。

总结

本题主要考察对矩阵遍历和条件判断的掌握。通过预先计算每个点在各个方向上连续 '1' 的数量，可以进一步优化算法的时间复杂度。