#include <iostream>
using namespace std;
const int N = 1010;
int g[N][N], f[N][N];
int n, m;
bool check(int x, int y, int len)
{
for(int i = x - len; i <= x; i++)
if(!g[i][y]) return false;
for(int j = y - len; j <= y; j++)
if(!g[x][j]) return false;
return true;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
{
cin >> g[i][j]; if(g[i][j]) f[i][j] = 1;
}
int res = 0;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
{
if(g[i][j] == 1)
{
if(g[i - 1][j - 1] == 1)
{
if(check(i, j, f[i - 1][j - 1])) f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j]);
}
}
res = max(res, f[i][j]);
}
cout << res * res << endl;
return 0;
}
f[i][j] = max(f[i - 1][j - 1] + 1, f[i][j])
为什么不能直接考虑左上角来直接递增正方形的边长呢,任意一个不都由上一个边长小1的转移而来吗