[文章目录]
Description
永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。 但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。 他希望找到一块最大的正方形无瑕疵土地来盖房子。 不过，这并不是什么难题，永恒の灵魂在10分钟内就轻松解决了这个问题。 现在，您也来试试吧。
又是一发神奇的动态规划。
dp[i][j]表示以i,j为右下角的正方形最长的边长。
得到转移方程：
如果map[i][j]==1，dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1;
若map[i][j]==0,dp[i][j]=0;进行dp，初值将第一行和第一列设成map
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int map[1100][1100],dp[1100][1100],ans=-1;
int read()
{
char ch=getchar();int re=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9') re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
map[i][j]=read();
for(int i=1;i<=n;i++) dp[i][1]=map[i][1],ans=max(ans,dp[i][1]);
for(int j=1;j<=m;j++) dp[1][j]=map[1][j],ans=max(ans,dp[1][j]);
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
{
if(map[i][j])
dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;
ans=max(dp[i][j],ans);
}
printf("%d",ans);
return 0;
}