Farmer John最近得到了面积为m×n的一大块土地，他想在这块土地上建造一所房子，这个房子必须是正方形的。但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。他希望找到一块最大的正方形无瑕疵土地来盖房子。不过，这并不是什么难题，Farmer John在10分钟内就轻松解决了这个问题。
现在，你也来试试吧。
第一行为两个整数m，n（1≤n，m≤100）。
接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。
一行，一个整数，最大正方形的边长。
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
2
容易想到，如果想确定一个正方形的面积 就需要确定这个正方形的四个顶点。
事实上，我们设$f[i][j]$为从$(1,1)$到$(i,j)$的范围内以$(i,j)$为一个顶点的最大的正方形的边长，可以得到，$f[i][j] = min \left \{ f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] \right \} + 1$。
#include <iostream> #define MAXN 101 #define MAXM 101 using namespace std; int m, n; bool a[MAXN][MAXM]; int f[MAXN][MAXM]; int ans; int main() { cin >> n >> m; for(register int i = 1; i <= n; i++) { for(register int j = 1; j <= m; j++) { cin >> a[i][j]; } } for(register int i = 1; i <= n; i++) { for(register int j = 1; j <= m; j++) { if(!a[i][j]) continue; f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1; ans = max(ans, f[i][j]); } } cout << ans; return 0; }
原文：https://www.cnblogs.com/kcn999/p/10847482.html
