USACO Home on the Range

最朴素的方法显然是枚举每个点，计算以该点为左上顶点的正方形的个数，不过，这种算法的复杂度是N^4的，对于N=250的数据有些吃力。

这时候，用到了一个常用思想：空间换时间

因此，本人down[i][j]表示(i,j)号方格向下数连续1的个数，这个数组可以在N^2时间内处理完毕。

然后，借助down数组计算以每个点为左上顶点的正方形的最大边长（用max_square函数实现），最后处理tot数组即可。

USACO题解上介绍了两种方法，Russ Cox的算法思路和本人几乎一致，后一个Greg Price给的算法更为巧妙。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MXN 255
05
06 char map[MXN][MXN];
07 int down[MXN][MXN];
08 unsigned long tot[MXN];
09 int n;
10
11 void init()
12 {
13     scanf("%d\n",&n);
14     int i;
15     for(i = 0;i < n;i ++)
16         fgets(map[i],255,stdin);
17 }
18
19 int get_min(int a,int b)
20 {
21     if(a < b)    return a;
22     return b;
23 }
24
25 int max_square(int i,int j)      //计算以(i,j)为左上定点的正方形的最大边长m
26 {
27     int dm,k;    //dm：横向长度为k时的长方形的纵向长度
28     int m;
29     for(dm = MXN,m = 0,k = 1;map[i][j + k - 1];k ++)
30     {
31         dm = get_min(dm,down[i][j + k - 1]);
32         if(get_min(dm,k) > m)    m = get_min(dm,k);
33         else break;
34     }
35     return m;
36 }
37
38 void solve()
39 {
40     int i,j;
41     for(i = n - 1;i >= 0;i --)
42         for(j = n - 1 ;j >= 0;j --)
43         {
44             if(map[i][j] == '1')
45             {
46                 down[i][j] = down[i + 1][j] + 1;
47             }
48             else
49                 down[i][j] = 0;
50         }
51     memset(tot,0,sizeof(tot));
52     for(i = 0;i < n;i ++)
53         for(j = 0;j < n;j ++)
54         {
55             if(map[i][j] == '1')
56                 tot[max_square(i,j)] ++;
57         }
58 }
59
60 void sum()    //把tot中的最大值转化为总数并输出
61 {
62     int i;
63     for(i = 250;i >= 2;i --)
64         tot[i] += tot[i + 1];
65     for(i = 2;i <= 250;i ++)
66     {
67         if(tot[i] > 0)    printf("%d %ld\n",i,tot[i]);
68         else break;
69     }
70 }
71
72 int main()
73 {
74     freopen("range.in","r",stdin);
75     freopen("range.out","w",stdout);
76     init();
77     solve();
78     sum();
79     fclose(stdin);
80     fclose(stdout);
81     return 0;
82 }