P1387 最大正方形 题解

P1387 最大正方形

简化题意

给定一个长 \(n\) 宽 \(m\) 的表格，其中每个格子上写有 \(0\) 或 \(1\)。
我们想要知道：这个表格中最大的完全由 \(1\) 组成的正方形的边长，即最大正方形的边长。

解题思路

这题运用的算法是动态规划。
我看其他人的题解，觉得有句话说的挺对，就是看到有二维的题要考虑一下 DP。

状态很明显，我们设 \(dp_{i, j}\) 为到表格第 \(i\) 行第 \(j\) 列的“最大正方形”的边长。

这里状态转移方程不是很好推。首先有一点：以 \((i, j)\) 为右下角的正方形，必须满足 \(a_{i, j} = 1\)。
然后，我们需要知道：如何靠一个角和前面的信息，推出整个最大正方形。我们知道，必需得到这 \((i - 1, j - 1)\)，\((i - 1, j)\)，\((i, j - 1)\) 这三个位置的情况才行。而此时这几个点都知道了。由于必须满足这三个点作为右下角构成的最大正方形边长都是 \(x\)，那么右下角为 \((i, j)\) 的最大正方形边长才能是 \(x + 1\)。这并不难，可以画图看看。

于是，我们发现一点：\((i, j)\) 为右下角的最大正方形的边长是由 \((i - 1, j)\)，\((i, j - 1)\)，\((i - 1, j - 1)\) 这三个格子为右下角组成的最大正方形的边长决定的。
由什么决定的呢？就是由它们三个的最小值决定的（因为必须满足最大正方形内部全都是 \(1\)，不能有 \(0\)，因此选最小的才能保证这点）。

最后推出的状态转移方程就是：

\[dp_{i, j} = min\{dp_{i - 1, j}, dp_{i, j - 1}, dp_{i - 1, j - 1}\} + 1 \]

所以代码就不难写了吧。

代码部分

#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0;
int a[110][110], dp[110][110];
int main()
{cin >> n >> m;for(int i = 1;i <= n;i ++)for(int j = 1;j <= m;j ++)cin >> a[i][j];for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){if(!a[i][j])dp[i][j] = 0;elsedp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;ans = max(ans, dp[i][j]);}}cout << ans << endl;return 0;
}