题意

思路

法一：枚举上下左右四个边界，利用二维前缀和，如果前缀和为0就成立
- 复杂度： $O(N^4)$
法二：枚举左右边界，对边界内的1按y排序，每两个相邻点+边界构成矩形
- 复杂度： $O(N^2*mlogm)$ ,(m为1的个数，最多到 $n^2$ )
法三：悬线法，将矩形中每个1视为黑点0视为无色点，每个点有一条向上的悬线悬线碰到黑点重新开始计算长度，对于每一条悬线，都有可能成为矩形的上下界
- $h[i][j]=a[i][j]==1?h[i-1][j]+1:0$ 求点(i,j)最长悬线度
- $l[i][j]=a[i][j]==1?l[i][j-1]+1:0$ 求点(i,j)向左最长延伸长度
- $r[i][j]=a[i][j]==1?r[i][j+1]+1:0$ 求点(i,j)向左最长延伸长度
- $L[i][j]=min(l[i][j],L[i-1][j])$ 求(i,j)所在的悬线向左最长延伸长度
- $R[i][j]=min(r[i][j],R[i-1][j])$ 求(i,j)所在的悬线向左最长延伸长度
- 使用 $ans[i][j]=h[i][j]*(L[i][j]+R[i][j])$ 得到结果
如果求正方形，悬线法求边长，边长长度为 $p[i][j]=min(h[i][j],L[i][j]+R[i][j]-1)$
- 复杂度： $O(NM)$
法四：求正方形， $f[i][j]$ 表示以 $(i,j)$ 作为正方形右下角，所获得的最大边长
- 提前维护每个点向上和向左有多少个连续0
- $f[i][j]=min(f[i-1][j-1]+1,h[i][j],l[i][j])$
- 复杂度： $O(NM)$