面積最大的全1子矩陣--九度OJ 1497，oj1497
- 題目描述：
-
在一個M * N的矩陣中，所有的元素只有0和1，從這個矩陣中找出一個面積最大的全1子矩陣，所謂最大是指元素1的個數最多。
- 輸入：
-
輸入可能包含多個測試樣例。
對於每個測試案例，輸入的第一行是兩個整數m、n(1<=m、n<=1000)：代表將要輸入的矩陣的大小。
矩陣共有m行，每行有n個整數，分別是0或1，相鄰兩數之間嚴格用一個空格隔開。
- 輸出：
-
對應每個測試案例，輸出矩陣中面積最大的全1子矩陣的元素個數。
- 樣例輸入：
-
2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
- 樣例輸出：0 4
解題思路：轉載自http://www.cnblogs.com/fstang/archive/2013/05/19/3087746.html
方法是：
1、先將0/1矩陣讀入x，對每一個非零元素x[i][j]，將其更新為：在本行，它前面的連續的1的個數+1（+1表示算入自身）
比如，若某一行為0 1 1 0 1 1 1，則更新為0 1 2 0 1 2 3
2、對每一個非零元素x[i][j]，在第j列向上和向下掃描，直到遇到比自身小的數，若掃描了y行，則得到一個大小為x[i][j]*(y+1)的全1子矩陣（+1表示算入自身所在行）
比如，若某一列為[0 3 4 3 5 2 1]'(方便起見，這裡將列表示成一個列向量)，我們處理這一列的第4個元素，也就是3，它向上可以掃描2個元素，向下可以掃描1個元素，於是得到一個4×3的全1子矩陣。
3、在這些數值中取一個最大的。
思想大概如下圖所示（空白處的0沒有標出）
對照步驟2中給出的例子，藍色的箭頭表示向上向下掃描，黑色的框表示最終得到的全1子矩陣
這樣做為什麼是對的？
想一想，對那個最大的全1子矩陣，用這種方法能不能找到它呢？——肯定可以。
一個最大全1子矩陣，肯定是四個邊界中的每一個都不能再擴展了，如下圖
假設圖中全1子矩陣就是最大子矩陣，則左邊界左側那一列肯定有一個或多個0（否則就可以向左邊擴展一列，得到一個更大的全1矩陣）
對其他3個邊界有類似的情況。
然後看圖中用黑圈標出的1（其特點是：和左邊界左側的某個0在同一行），從這個1出發，按照之前的方法，向上向下掃描，就可以得到這個子矩陣。所以，肯定可以找到。
下面是我的代碼，實際實現的時候，為了提高效率，估計了一下upperbound，這個upperbound就是：在當前列，
包含x[i][col]的連續的非零序列的和，比如對某列[0 3 4 3 5 2 1]'，後面6個的upperbound都是
3 + 4 + 3 + 5 + 2 + 1 = 18，對於0元素，不需要upperbound
![]()
1 #include<iostream>
2 using namespace std;
3
4 int main()
5 {
6 int n,m;
7 while(cin>>n>>m){
8 int **array=new int*[n];
9 int **upperbound=new int*[n];
10 for(int i=0;i<n;i++){
11 array[i]=new int[m];
12 upperbound[i]=new int[m];
13 for(int j=0;j<m;j++){
14 cin>>array[i][j];
15 upperbound[i][j]=0;
16 }
17 }
18 //prepare:
19 for(int i=0;i<n;i++){
20 for(int j=1;j<m;j++){
21 if(array[i][j]==1&&array[i][j-1]!=0)array[i][j]=array[i][j-1]+1;
22 }
23 }
24 //計算upperbound
25 for(int j=0;j<m;j++){
26 for(int i=0;i<n;i++){
27 if(array[i][j]==0)continue;
28 else{
29 int sum=0,temp=i;
30 while(temp<n&&array[temp][j]>0){
31 sum+=array[temp][j];
32 temp++;
33 }
34 for(int k=i;k<temp;k++){
35 upperbound[k][j]=sum;
36 }
37 i=temp;
38 }
39 }
40 }
41
42 int maxarea=0;
43 for(int i=0;i<n;i++){
44 for(int j=0;j<m;j++){
45 if(array[i][j]!=0&&maxarea<upperbound[i][j]){
46 int cnt=1,val=array[i][j];
47 for(int row=i-1;row>0;row--){
48 if(array[row][j]>=val)cnt++;
49 else
50 break;//這裡一定要break
51 }
52 for(int row=i+1;row<n;row++){
53 if(array[row][j]>=val)cnt++;
54 else
55 break;//這裡一定要break
56 }
57 if(cnt*val>maxarea)maxarea=cnt*val;
58 }
59 }
60 }
61 cout<<maxarea;
62 }
63 return 0;
64
65 }
View Code
