# 1139. Largest 1-Bordered Square解题思路分析

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

```public int largest1BorderedSquare(int[][] grid) {
int[][] memo_r = new int[grid.length][grid[0].length]; // 横向前缀和
int[][] memo_c = new int[grid.length][grid[0].length]; // 纵向前缀和
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
if(c==0){
memo_c[r][c] = grid[r][c];
}else{
memo_c[r][c] = memo_c[r][c-1] + grid[r][c];
}
if(r==0){
memo_r[r][c] = grid[r][c];
}else{
memo_r[r][c] = memo_r[r-1][c] + grid[r][c];
}
}
}
int res = 0; // 结果
for(int r=0;r<grid.length;r++){ // 循环纵坐标
for(int c=0;c<grid[0].length;c++){ // 循环横坐标
int value = grid[r][c]; // 当前点
if(value==0){ // 顶点为0直接略过
continue;
}
// 防止正方形越界，计算当前点到底边和右边的最小值作为正方形最大边长。
int maxLength = Math.min(grid.length - r, grid[0].length - c);
for(int i = 0; i<maxLength;i++){
int top = memo_r[r+i][c] - memo_r[r][c] + value;
int bottom = memo_r[r+i][c+i] - memo_r[r][c+i] + value;
int left = memo_c[r][c+i] - memo_c[r][c] + value;
int right = memo_c[r+i][c+i] - memo_c[r+i][c] + value;
// 四条边之和是否等于周长
if(top+bottom+left+right == (i+1) * 4){
res = Math.max(res, (i+1)*(i+1)); // 更新结果
}
}
}
}
return res;
}```