题解

思路

固定边长 $l$ 后，把高度不小于 $l$ 的格子视为可用格子。问题变成：是否存在一个 $l\times l$ 的全可用正方形。

若边长 $l$ 可行，则所有更小的边长也可行，因此答案具有单调性，可以二分。

做法

在一次判定中，令 dp[i][j] 表示以 $(i,j)$ 为右下角、全部格子高度不小于当前阈值的最大正方形边长。若当前格子可用，则

$$dp[i][j]=1+\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);$$

否则为零。只要某个状态达到待判定的 $l$ 即可返回可行。

极小规模可以枚举正方形位置、边长和内部所有格子。若高度只为 $1$ 或 $10^6$，则边长至少为 2 的答案不能包含高度 1，直接求高格组成的最大全正方形即可。

正确性证明

阈值判定 DP 是经典的最大全一正方形递推：一个边长至少为 2 的正方形可行，当且仅当当前格子可用且其上、左、左上三个相邻正方形均能提供至少少一层的边长。因此判定准确。

可行正方形的任意更小子正方形仍满足高度下界，故可行性关于 $l$ 单调。二分返回的最大可行值因此恰为题目答案。

复杂度分析

每次判定为 $O(nm)$，共判定 $O(\log\min(n,m))$ 次；总时间复杂度为 $O(nm\log\min(n,m))$，空间复杂度为 $O(m)$。