[USACO]Home on the Range

 1 // File Name: range.c
 2 // Author: darkdream
 3 // Created Time: 2014年04月07日 星期一 17时23分06秒
 4 /*
 5 ID: dream.y1
 6 PROG: range
 7 LANG: C++
 8 */
 9 #include<stdio.h>
10 #include<string.h>
11 #include<stdlib.h>
12 #include<time.h>
13 #include<math.h>
14 #include<limits.h>
15 
16 int map[300][300];
17 int hang[300][300];
18 int lie[300][300];
19 int dp[4][251][251];
20 int main(){
21 
22    freopen("range.in","r",stdin);
23    freopen("range.out","w",stdout);
24    
25     
26    int n ; 
27    scanf("%d",&n);
28    memset(hang,0,sizeof(hang));
29    memset(lie,0,sizeof(lie));
30    memset(dp,0,sizeof(dp));
31    for(int i =1 ;i <= n;i ++)
32       for(int j = 1;j <= n;j ++)
33           scanf("%1d",&map[i][j]);
34    for(int i = 1;i <= n;i ++)
35    {
36      for(int j = 1;j <= n;j ++)
37      {
38        if(map[i][j])
39            hang[i][j] = hang[i][j-1] + 1;
40      }
41    }
42    for(int i = 1;i <= n;i ++)
43    {
44      for(int j = 1;j <= n;j ++)
45      {
46        if(map[j][i])
47            lie[j][i] = lie[j-1][i] + 1;
48      }
49    }
50  /* for(int i = 1;i<= n;i ++)
51   {
52     for(int j = 1;j <= n;j ++)
53         printf("%d ",hang[i][j]);
54     printf("\n");
55   }
56     printf("\n");
57   for(int i = 1;i<= n;i ++)
58   {
59     for(int j = 1;j <= n;j ++)
60         printf("%d ",lie[i][j]);
61     printf("\n");
62   }
63     printf("\n");*/
64    int ans[300];
65    memset(ans,0,sizeof(ans));
66    for(int i = 2; i <= n;i ++)
67    {
68      for(int j = 2;j <= n; j ++)
69      {
70           int k = hang[i][j] > lie[i][j]?lie[i][j]:hang[i][j];
71           if(map[i-1][j-1])
72               dp[1][j-1][1] = 1; 
73 
74           for(int s = 2;s <= k ; s ++ )
75               dp[2][j][s] += dp[1][j-1][s-1];
76 
77      }
78         for(int j = 2;j <= n;j ++)
79           for(int s = 2;s <= n;s ++)
80            {
81               ans[s] +=  dp[2][j][s];
82            }
83 
84            memcpy(dp[1],dp[2],sizeof(dp[2]));
85            memcpy(dp[2],dp[3],sizeof(dp[3]));
86    }
87 
88   for(int i =2;i <= n;i ++)
89       if(ans[i])
90           printf("%d %d\n",i,ans[i]);
91 return 0 ;
92 }