每日c/c++题 备战蓝桥杯(洛谷P1387 最大正方形)

洛谷P1387 最大正方形 题解

题目描述

给定一个 $n\times m$ 的01矩阵，要求找出其中全由1组成的最大正方形的边长。

输入格式
第一行两个整数 $n,m$
接下来 $n$ 行每行 $m$ 个0或1的数，表示矩阵

输出格式
输出最大正方形的边长

数据范围
$1\le n,m\le 100$

解题思路

错误代码分析（DFS解法）

用户提供的DFS代码存在逻辑错误，主要问题如下：

1. 递归方向错误：DFS应向四个方向扩展，但代码仅向右下扩展，无法覆盖所有可能情况
2. 状态管理混乱：使用全局变量x1和yy记录起点，在递归过程中会被覆盖
3. 边界判断缺失：未正确处理矩阵边界情况
4. 时间复杂度高：最坏情况时间复杂度为 $O(n^2{m}^2)$，会超时

正确解法：动态规划（DP）

核心思想：
用dp[i][j]表示以(i,j)为右下角的最大正方形边长。当matrix[i][j] == 1时：
$$dp[i][j]=\min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1$$

状态转移解释：
当前格子能构成的正方形边长由上方、左方、左上方三个方向的最小值决定，这保证了正方形的完整性。

边界条件：

• 当i=0或j=0时，dp[i][j] = matrix[i][j]（第一行/列单独处理）

代码实现（优化版）

#include <bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> matrix(n+1, vector<int>(m+1));vector<vector<int>> dp(n+1, vector<int>(m+1, 0));int max_side = 0;// 输入处理（从1开始索引）for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) {cin >> matrix[i][j];}}// 动态规划求解for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) {if(matrix[i][j] == 1) {dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;max_side = max(max_side, dp[i][j]);}}}cout << max_side << endl;return 0;
}

算法分析

• 时间复杂度：$O(nm)$，只需遍历矩阵一次
• 空间复杂度：$O(nm)$，可优化至$O(m)$（滚动数组）
• 正确性证明：通过数学归纳法可证明状态转移方程的正确性

优化技巧

1. 空间优化：使用滚动数组将空间复杂度降至$O(m)$
2. 提前终止：当剩余空间不足以超过当前最大值时提前终止
3. 输入优化：使用快速读入处理大数据

示例演示

输入样例：

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 1 1

处理过程：

1. 初始化dp数组全为0
2. 遍历到(1,2)时，dp[1][2]=1
3. 遍历到(2,2)时，dp[2][2]=min(0,1,0)+1=1
4. 遍历到(2,3)时，dp[2][3]=min(1,1,0)+1=1
5. 最终在(4,4)处得到最大边长3

输出：

3

总结

本题是典型的动态规划应用场景，通过状态转移方程巧妙地将二维问题降维处理。相比暴力DFS解法，DP方案在时间和空间效率上都有显著优势。实际编程时需注意：

1. 矩阵索引从1开始处理更方便
2. 使用min({a,b,c})语法需要C++11及以上标准
3. 边界条件需要单独处理

建议掌握该问题的DP解法，并尝试实现空间优化版本以加深理解。