标签归档：盖房子

盖房子

发表回复

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