DP问题,计算每个点的状态值,状态表示为该点向左上方能延伸组成的正方形的最大边长
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N]; //f[i][j]表示该点所能表示的正方形的最大边长
int main()
{
int res = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
int w;
scanf("%d", &w);
if (w) //只有w等于1的情况下才需要状态计算
{
f[i][j] = min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) + 1;
res = max(res, f[i][j]);
}
}
printf("%d\n", res * res); //最后输出正方形面积=边长的平方
return 0;
}
刷到佬的题解啦,tql