首页 > > 程序设计 > C/C++ >

New Land LightOJ - 1424

2018-06-17 21:41:12来源：未知阅读 ()

题意：找出01矩阵中最大的完全由0组成的矩阵。

方法：

重点在于转化。

先预处理(i,j)点向上最长能取到的连续的全0条的长度。然后枚举某一行作为矩阵的最下面一行，就可以把题目转化为LOJ-1083。用那道题的任意一种方法做即可。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[2010][2010],s1[2010][2010],left[2010],right[2010];
 5 int ans,TT,T,m,n;
 6 int main()
 7 {
 8     int i,j;
 9     scanf("%d",&T);
10     for(TT=1;TT<=T;TT++)
11     {
12         ans=0;
13         scanf("%d%d",&m,&n);
14         for(i=1;i<=m;i++)
15             for(j=1;j<=n;j++)
16                 scanf("%1d",&a[i][j]);
17         for(i=1;i<=m;i++)
18             for(j=1;j<=n;j++)
19                 if(a[i][j]==1)
20                     s1[i][j]=0;
21                 else
22                     s1[i][j]=s1[i-1][j]+1;
23         for(i=1;i<=m;i++)
24         {
25             for(j=1;j<=n;j++)
26             {
27                 left[j]=j;
28                 while(left[j]>1&&s1[i][left[j]-1]>=s1[i][j])    left[j]=left[left[j]-1];
29             }
30             for(j=n;j>=1;j--)
31             {
32                 right[j]=j;
33                 while(right[j]<n&&s1[i][right[j]+1]>=s1[i][j])    right[j]=right[right[j]+1];
34             }
35             for(j=1;j<=n;j++)
36                 ans=max(ans,s1[i][j]*(right[j]-left[j]+1));
37         }
38         printf("Case %d: %d\n",TT,ans);
39     }
40     return 0;
41 }