题解 | 边界都是1的最大正方形大小

package main

import (
    "fmt"
)

func main() {
    row := 0
    for {
        n, _ := fmt.Scan(&row)
        col := row
        if n == 0 {
            break
        } else {
            arr := make([][]int, row)
            for i:=0; i<row; i++ {
                arr[i] = make([]int, col)
                for j:=0; j<col; j++ {
                    fmt.Scan(&arr[i][j])
                }
            }

            right := make([][]int, row)
            down := make([][]int, row)
            for i:=0; i<row; i++ {
                right[i] = make([]int, col)
                down[i] = make([]int, col)
            }           
		  // 构建右矩阵，arr[i][j] 代表i，j从右往左连续1的个数（1构建的边长）
            for i:=row-1; i>=0; i-- {
                for j:=col-1; j>=0; j-- {
                    if arr[i][j] == 1 {
                        if j+1 < col {
                            right[i][j] = right[i][j+1] + 1
                        } else {
                            right[i][j] = 1
                        }
                    }
                }
            }
		  // 构建下矩阵，arr[i][j] 代表i，j从上往下连续1的个数（1构建的边长）
            for j:=0; j<col; j++ {
                for i:=row-1; i>=0; i-- {
                    if arr[i][j] == 1 {
                        if i+1 < row {
                            down[i][j] = down[i+1][j] + 1
                        } else {
                            down[i][j] = 1
                        }
                    }
                }
            }
            maxl := 0
            for i:=0; i<row; i++ {
                for j:=0; j<col; j++ {
                    if arr[i][j] == 1 { // 当前为1这个点时开始判断正方形最大边长
					  // 边长为1时-（边长可取的最大值min(col-j, row-i)）范围内查找是否满足正方形
                        for board := 1; board <= min(col-j, row-i); board++ {
                          // i，j 这个点  right[i][j] 代表i，j这个点（从左往右的边长）边长大于需要的board
						  // i，j 这个点  down[i][j] 代表i，j这个点（从上往下的边长）边长大于需要的board
						  if right[i][j] >= board && 
                               down[i][j] >= board {
								 // 此时只需要判断[i+board-1，j] 这个点从左往右的边长, right[i+board-1][j]边长大于需要的board
								 // 此时只需要判断[i，j+board-1] 这个点从上往下的点边长
								 // down[i][j+board-1]大于需要的board 
								 // 都满足则认为找到最大边长，更新最大值
                                if i+board-1 < row && j+board-1 < col {
                                    if right[i+board-1][j] >=board && down[i][j+board-1] >= board {
                                        maxl = max(maxl, board)
                                    }
                                }
                            }
                        }

                    }
                }
            }
            fmt.Println(maxl)
        }
    }
}
func min(a, b int) int {
    if a<b {
        return a
    }
    return b
}
func max(a, b int) int {
    if a>b {
        return a
    }
    return b
}