盖房子
【问题描述】
永恒の灵魂最近得到了面积为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
【代码】
#include
#include
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;
}