题目描述

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

样例

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

输入：grid = [[1,1,0,0]]
输出：1

限制

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] 为 0 或 1

算法

(预处理，枚举) $O(n * m * \min(n, m))$

1. 我们枚举每一个子正方形：三重循环，第一重循环枚举正方形的长度 len，第二三重循环枚举左上角的顶点。
2. 对于每个正方形，我们需要在常数时间内判断是否合法，这里我们提前预处理：sum_r[i][j] 表示第 i 行前 j 列数字的和，sum_c[j][i] 表示第 j 列前 i 行的和，这里的 i 和 j 都从下标 1 开始。
3. 判断时，我们仅需要判断四条边的区间和是不是等于 len。

时间复杂度

• 预处理的时间复杂度为 $O(nm)$，枚举的时间复杂度为 $O(n * m * \min(n, m))$，故总时间复杂度为 $O(n * m * \min(n, m))$。

空间复杂度

• 需要额外 $O(nm)$ 的空间记录前缀和。

C++ 代码

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> sum_r(n + 1, vector<int>(m + 1, 0));
        vector<vector<int>> sum_c(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                sum_r[i][j] = sum_r[i][j - 1] + grid[i - 1][j - 1];

        for (int j = 1; j <= m; j++)
            for (int i = 1; i <= n; i++)
                sum_c[j][i] = sum_c[j][i - 1] + grid[i - 1][j - 1];

        for (int len = min(n, m); len >= 1; len--) {
            for (int i = 0; i < n - len + 1; i++)
                for (int j = 0; j < m - len + 1; j++) {
                    int x = i + len - 1, y = j + len - 1;
                    if (sum_r[i + 1][y + 1] - sum_r[i + 1][j] == len
                     && sum_r[x + 1][y + 1] - sum_r[x + 1][j] == len
                     && sum_c[j + 1][x + 1] - sum_c[j + 1][i] == len
                     && sum_c[y + 1][x + 1] - sum_c[y + 1][i] == len)
                        return len * len;
                }
        }
        return 0;
    }
};