题目链接：传送门

Description

小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。 不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。 于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？

Input

包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。

Output

包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含的）。

Solution

我们可以先将横纵坐标合为偶数的点取反，这样这道题就变成了求最大子正方形最大子矩形的问题

第一问非常简单，设Dp[i][j]Dp[i][j]表示到（i,j）的最大子正方形的边长，

如果A[i][j]=A[i−1][j]=A[i][j−1]=A[i−1][j−1]A[i][j] =A[i - 1][j] = A[i][j - 1] = A[i - 1][j - 1]，

则Dp[i][j]=min(Dp[i−1][j],Dp[i][j−1],Dp[i−1][j−1])+1Dp[i][j] = min(Dp[i - 1][j], Dp[i][j - 1], Dp[i - 1][j - 1]) + 1

答案一边算一边取最大值即可

第二问的话自己想没想出来，看了题解之后发现是一种新的算法：

悬线法（又是一个听起来特别高端的名字） ，特别详细的做法和证明等百度上都有

主要思路是先预处理出up[i][j]up[i][j]表示（i，j）向上扩展最多能扩展几行，down[i][j]down[i][j]表示（i，j）向下扩展最多能扩展几行

然后我们首先枚举每一行，每一列，在第i行中，记max_lenth表示枚举到第j列时最多横向能扩展的列数，max_up和max_down分别表示能向上、向下扩展多少行

这样的话,max_up和max_down就分别等于在这max_lenth列中up[i][j]up[i][j]和down[i][j]down[i][j]的最小值

然后答案一边枚举一边更新即可

复杂度是O(NM)O(NM)的 又学到了一种新的算法