#10. 01 矩阵 I

给定一个 行 列的 矩阵 ，求其最大的全 子正方形的边长。

更准确地说，求满足下式的最大整数 ：

第一行两个整数 。

接下来 行，每行 个整数（ 或 ），表示矩阵的各个元素。

一行一个整数，表示最大全 子正方形的边长。

样例输入

5 5
0 1 1 1 1
1 0 1 1 1
1 1 1 1 1
0 0 0 1 1
1 1 1 1 0

样例输出

3

。

本题按子任务计分，每个子任务采用 min 计分 —— 任一测试点未通过则整个子任务记 分，后续子任务仍继续评测：

算法建议：经典 DP 即可满分。设 dp[i][j] 为以 为右下角的全 正方形最大边长，则

dp[i][j] = (A[i][j] == 1) ? 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) : 0

另外两种可参考的解法：

• 朴素 ：枚举左上角，依次扩边，遇到 即停止。
• 直方图 + 段树 ：逐行构建以该行为底的高度直方图；对每个高度做线段树范围最小值 + 二分，定位最大正方形边长。

第 2、5 子任务中存在「差一点」的输入：最大正方形边长为 ，但存在一个关键 —— 只要把它改成 ，答案就会跳到 。这种用例会考验 DP 在「边界 +1」类分支上的健壮性。