题目如果侵权请马上告知，关于该题的内容会立即删除。

「LuoguOJ P1387」最大正方形

时间限制：1000ms        空间限制：128MB

题意简述

有一个 N * M 的矩阵，矩阵中每个元素的值为 0 或 1。

在矩阵中找出一个边长尽可能大的正方形，使得正方形内元素全是 1，求出这个边长。

1 ≤ N, M ≤ 100。

题目分析

动态规划算法我们暂且不研究，因为看这题的数据范围并不需要这么做。

先抛出暴力算法：

• 枚举左端点的横纵坐标，再枚举正方形的边长（这一步是为了确定正方形）

• 判断这个正方形内的元素是否全为 1。

这个做法的时间复杂度是一个包含 N, M 的五次式，显然无法通过。

但上面的做法，其实是可以优化的。

如果给出正方形的左上、右下端点的时候，程序能够只算一次就判断正方形的元素是否全为 1，那么时间复杂度就可以降成 包含 N, M 的三次式，足以通过本题。

现在谈谈怎么快速判断。

显然，假设现在枚举到的正方形边长为 K，那么如果这个正方形元素和为 K * K，那么就可以证明这个正方形元素全是 1。

那判断的时候只需要看矩阵的元素和是否等于边长的平方即可。 

之前说过如何快速求一序列中任意子序列的和（用前缀和），那如何在一矩阵中快速求出任意子矩阵的和 ？

这就可以使用二维前缀和了。

按照套路，设 S(a, b) 为左上端点为 (1, 1)，右下端点为 (a, b) 的矩阵元素和。

图 1

如图 1，我们想求出 S(m, n) （即整个矩阵面积），下面标出了图中的几个数据：

• 红色 部分元素和：S(m - 1, n - 1)

• 红色 + 黄色 部分元素和：S(m - 1, n)

• 红色 + 绿色 部分元素和：S(m, n - 1)

• 蓝色 部分：新加的元素，以 a 表示

那么，整体面积就可以这么表示：

   S(m, n) 

= 红色部分 + 黄色部分 + 绿色部分 + 蓝色部分

= （红色部分 + 黄色部分）+ （红色部分 + 绿色部分）+ 蓝色部分 - 红色部分

= S(m - 1, n) + S(m, n - 1) + a - S(m - 1, n - 1)

前半部分已经完成，而快速查询子矩阵元素和的步骤应该也可以利用容斥原理推出。

要求以 (a, b) 为左上角，(c, d) 为右下角的矩形 (蓝色部分) 的元素和。 

按照同样的套路，通过拆添项解决问题。

   蓝色部分

= 整体部分 - 红色部分 - 黄色部分 - 绿色部分

= 整体部分 - （红色部分 + 黄色部分） - （红色部分 + 绿色部分） + 红色部分

= S(c, d) - S(a - 1, d) - S(c, b - 1) + S(a - 1, b - 1)

因此，就可以以 O(n × m) 的复杂度完成前缀和预处理，O(1) 完成单区间查询。

现在回到刚才的问题上。

其实做完前缀和预处理后，只需要枚举三个数：正方形的左上角端点坐标（两个数）、正方形的边长。

而每个枚举的正方形都可以利用二维前缀和快速判断这个正方形元素和是否等于边长的平方。

最后统计一下这个矩形有多少个合法的子正方形，最后输出即可。

2021/5/7 更新：评论指出原文的一个错误，现已修改。