【问题描述】
永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。
但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。
他希望找到一块最大的正方形无瑕疵土地来盖房子。
不过，这并不是什么难题，永恒の灵魂在10分钟内就轻松解决了这个问题。
现在，您也来试试吧。
【输入格式 Input Format】
输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。
【输出格式 Output Format】
一个整数，最大正方形的边长。
【样例输入 Sample Input】
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
【样例输出 Sample Output 】
2
【算法分析】
状态方程就是.f[i,j]=min{f[i-1,j],f[i,j-1],f[i-1,j-1]}+1;
f[i,j]表示的是 右下角坐标为(i,j)的正方形边长是f[i,j]
只要从左到右从上到下的2重循环就可以解决叻.
应该容易理解吧.
就贴一下Example Date运行后的F数组值
0 1 1 1
1 1 2 0
0 1 2 0
1 1 0 1
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <stdio.h> #include <string.h> int a[1002][1002], f[1002][1002]; int main() { int i, j, n, m, max = -1; scanf("%d%d", &n, &m); memset(a, 0, sizeof(a)); memset(f, 0, sizeof(f)); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf("%d", &a[i][j]); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (a[i][j] == 1) { f[i][j] = f[i - 1][j]; if (f[i][j] > f[i][j - 1]) f[i][j] = f[i][j - 1]; if (f[i][j] > f[i - 1][j - 1]) f[i][j] = f[i - 1][j - 1]; f[i][j] = f[i][j] + 1; } else f[i][j] = a[i][j]; if (f[i][j] > max) max = f[i][j]; } } printf("%d\n", max); return 0; } |