# 1139.最大的以1为边界的正方形

## 问题描述
[1139. 最大的以 1 为边界的正方形 (Medium)](https://leetcode.cn/problems/largest-1-bordered-square/)

给你一个由若干 `0` 和 `1` 组成的二维网格 `grid`，请你找出边界全部由 `1` 组成的最大 **正方形**
子网格，并返回该子网格中的元素数量。如果不存在，则返回 `0`。
**示例 1：**
```
输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9
```
**示例 2：**
```
输入：grid = [[1,1,0,0]]
输出：1
```
**提示：**
- `1 <= grid.length <= 100`
- `1 <= grid[0].length <= 100`
- `grid[i][j]` 为 `0` 或 `1`

## 解题思路
利用前缀和来简化满足正方形条件的计算，枚举正方形边长，找到最大的`l`，再和已经得出的结果进行比较。

## 代码
```cpp
class Solution {
  public:
    int largest1BorderedSquare(vector<vector<int>> &grid) {
        // 前缀和
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> sum_row(m, vector<int>(n + 1, 0)); // 每行前缀和
        vector<vector<int>> sum_col(m + 1, vector<int>(n, 0)); // 每列前缀和
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 1; j <= n; j++) {
                sum_row[i][j] = sum_row[i][j - 1] + grid[i][j - 1];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                sum_col[i][j] = sum_col[i - 1][j] + grid[i - 1][j];
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int l = res + 1; l <= std::min(i, j); l++) { // 直接从res开始
                    if (sum_col[i][j - 1] - sum_col[i - l][j - 1] == l && sum_row[i - 1][j] - sum_row[i - 1][j - l] == l && sum_col[i][j - l] - sum_col[i - l][j - l] == l && sum_row[i - l][j] - sum_row[i - l][j - l] == l)
                        res = std::max(l, res);
                }
            }
        }
        return res * res;
    }
};
```