面積最大的全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