面积最大的全1子矩阵

时间限制：1 秒

内存限制：128 兆

特殊判题：否

提交：859

解决：179

题目描述：

在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多。

 

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小。
矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间严格用一个空格隔开。

 

输出：

对应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数。

 

样例输入：

2 20 00 04 40 0 0 00 1 1 00 1 1 00 0 0 0

样例输出：

04

来源：

腾讯2012年暑期实习生招聘面试二面试题

从19：42----22：43.。。我也是醉了！

唉。。。

队友代码：

 1 #include<stdio.h> 2   3 int dp[1005][1005],a[1005][1005]; 4   5 int main() 6 { 7     int n,m; 8     for(int i=0;i<=1000;i++) 9         dp[0][i]=dp[i][0]=0;10     while(scanf("%d%d",&n,&m)>0)11     {12         for(int i=1;i<=n;i++)13             for(int j=1;j<=m;j++)14             scanf("%d",&a[i][j]);15         int sum=0;16         for(int i=1;i<=m;i++)17         {18             sum+=a[1][i]; dp[1][i]=sum;19         }20         for(int i=2;i<=n;i++)21         {22             sum=0;23             for(int j=1;j<=m;j++)24             {25                sum+=a[i][j]; dp[i][j]=dp[i-1][j]+sum;26             }27         }28         int maxk=0;29         for(int i=n;i>0;i--)30         for(int j=m;j>0&&maxk<i*j;j--)31         if(a[i][j])32         {33             int r=1,c=1;34             while(j-c>=0)35             {36                 if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c)37                 {38                      if(maxk<r*c) maxk=r*c; c++;39                 }40                 else41                     break;42             }43             while(i-r>=0&&c>0)44             {45                 if(dp[i][j]-dp[i][j-c]-dp[i-r][j]+dp[i-r][j-c]==r*c)46                 {47                     if(maxk<r*c) maxk=r*c; r++;48                 }49                 else50                     c--;51             }52         }53         printf("%d\n",maxk);54     }55 }56  57 /**************************************************************58     Problem: 149759     User: aking201560     Language: C++61     Result: Accepted62     Time:410 ms63     Memory:8912 kb64 ****************************************************************/

View Code

 

  1 #include <stdio.h>  2 #include <string.h>  3 #include <algorithm>  4 using namespace std;  5    6 int map[1005][1005];  7 int col[1005][1005];  8 int n,m,maxn;  9   10 void set_col(int p) 11 { 12     int i,j,sum; 13     for(i = 1; i<=n; i++) 14     { 15         if(!map[i][p]) 16             continue; 17         j = i; 18         sum = 0; 19         while(map[j][p] && j<=n) 20         { 21             sum+=map[j][p]; 22             j++; 23         } 24         for(int k = i; k<j; k++) 25             col[k][p] = sum; 26         i = j; 27     } 28 } 29   30 int find(int r,int c) 31 { 32     int i,j,val=map[r][c]; 33     int cnt = 1; 34     for(i = r-1; i>0; i--) 35     { 36         if(val>map[i][c]) 37             break; 38         cnt++; 39     } 40     for(i = r+1; i<=n; i++) 41     { 42         if(val>map[i][c]) 43             break; 44         cnt++; 45     } 46     return val*cnt; 47 } 48   49 int solve() 50 { 51     int i,j; 52     maxn = 0; 53     for(i = 1; i<=n; i++) 54     { 55         for(j = 1; j<=m; j++) 56         { 57             if(maxn<col[i][j] && map[i][j]) 58             { 59                 int val = find(i,j); 60                 maxn = max(maxn,val); 61             } 62         } 63     } 64     return maxn; 65 } 66   67 int main() 68 { 69     int i,j; 70     while(~scanf("%d%d",&n,&m)) 71     { 72         for(i = 1; i<=n; i++) 73         { 74             for(j = 1; j<=m; j++) 75                 scanf("%d",&map[i][j]); 76         } 77         for(i = 1; i<=n; i++) 78         { 79             for(j = 2; j<=m; j++) 80             { 81                 if(map[i][j]==1 && map[i][j-1]) 82                     map[i][j]=map[i][j-1]+1; 83             } 84         } 85         for(i = 1; i<=m; i++) 86             set_col(i); 87         printf("%d\n",solve()); 88     } 89   90     return 0; 91 } 92   93 /************************************************************** 94     Problem: 1497 95     User: aking2015 96     Language: C++ 97     Result: Accepted 98     Time:440 ms 99     Memory:8912 kb100 ****************************************************************/

View Code

 

我的代码：

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5   6 int num[1005][1005]; 7  8 int len[1005][1005]; 9 int main()10 {11     int m,n;12     int i,j;13 14     while(scanf("%d%d",&m,&n)!=EOF)15     {16         for(i=1; i<=m; i++)17         {18 19             len[i][0]=0;20             for(j=1; j<=n; j++)21             {22                 scanf("%d",&num[i][j]);23 24                 len[i][j]=len[i][j-1]+num[i][j];25             }26         }27 28         int mmax=0,x;29         for(i=m; i>0; i--)30         {31             for(j=n; j>0; j--)32             {33  34                 if(num[i][j]&&i*j>mmax)35                 {36                     int h=0,w=0;37 38                     int k;39                     int ww=100000;40                     for(x=i; x>0; x--)41                     {42                         if(!num[x][j]) break;43                         h++;44                         w=0;45  46                         for(k=j; k>0; k--)47                         {48                             if(len[x][k]==j)49                             {50                                 w=j;51                                 break;52                             }53                             else if(num[x][k]&&len[x][j]-len[x][k]+1==j-k+1&&w<=ww)54                             {55                                 w++;56                             }57                             else break;58                         }59  60                         ww=min(w,ww);61                         mmax=max(mmax,ww*h);62 63                     }64  65  66                 }67  68             }69         }70         printf("%d\n",mmax);71     }72     return 0;73 }74 /**************************************************************75     Problem: 149776     User: aking201577     Language: C++78     Result: Accepted79     Time:440 ms80     Memory:9408 kb81 ****************************************************************/

View Code

说多了，都是泪。。。。。。。。