动态规划实现：0-1矩阵的特殊最大正方形求解问题

问题说明 #

给定一个由0和1构成的矩阵，需要找出其中最大的正方形：

• 正方形的四个角位置可以是0或1，无限制
• 除四个角外，正方形内的所有其他位置必须全为1
  最终返回该正方形的左上角坐标与右下角坐标。

示例 #

输入矩阵 #

0 0 0 1 0 0
0 1 1 1 1 1
1 0 0 1 0 0
1 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0

输出结果 #

((0, 2), (2, 4))

实操解法 #

1. 从大到小排查边长：先尝试矩阵能容纳的最大正方形边长（取矩阵行数和列数中的较小值），找到符合条件的就直接返回，不用再看更小的边长，效率最高。
2. 遍历所有可行的左上角：对每个候选边长k（对应正方形的边长为k，即从左上角(i,j)到右下角(i+k-1,j+k-1)），遍历所有能放下该正方形的左上角坐标(i,j)。
3. 验证正方形合规性：
   • 四个角无需检查，0或1都符合要求
   • 检查上边缘（除左右角）：行i，列j+1到j+k-2的所有元素必须是1
   • 检查下边缘（除左右角）：行i+k-1，列j+1到j+k-2的所有元素必须是1
   • 检查左边缘（除上下角）：列j，行i+1到i+k-2的所有元素必须是1
   • 检查右边缘（除上下角）：列j+k-1，行i+1到i+k-2的所有元素必须是1
   • 检查内部区域：行i+1到i+k-2，列j+1到j+k-2的所有元素必须是1
4. 找到即返回：因为是从大到小排查的，第一个符合条件的正方形就是最大的，直接返回它的坐标即可。

示例验证 #

拿给出的示例来说，最大的合规正方形是边长为3的正方形：

• 左上角(0,2)，右下角(2,4)
• 四个角分别是0、0、0、0，符合要求
• 上边缘中间(0,3)=1，下边缘中间(2,3)=1，左边缘中间(1,2)=1，右边缘中间(1,4)=1，内部(1,3)=1，全部为1，满足条件。

内容的提问来源于stack exchange，提问作者Sach