プログラム・プロムナード 最大長方形の面積

下記の連載「プログラム・プロムナード」には，有益なアルゴリズムが色々と載っているので実装してみました．

プログラム・プロムナード
http://www.ipsj.or.jp/07editj/promenade/index.html

2002年4月号 最大長方形の面積(和田英一)

view plainprint?

1. import java.util.*;  
2. import java.awt.*;  
3.   
4. public class Main{  
5.   
6.  // 単純なループによる実装 O(n^6)  
7.  private int count1(int[][] a){  
8.   int res=0;  
9.   int m=a[0].length;  
10.   int n=a.length;  
11.   for(int y1=0;y1<n;y1++){  
12.    for(int x1=0;x1<m;x1++){  
13.     // 始点-(x1, y1)  
14.     for(int y2=y1;y2<n;y2++){  
15.      for(int x2=x1;x2<m;x2++){  
16.       // 終点-(x2, y2)  
17.       int c=0;  
18.       // (x1, y1)-(x2, y2)から構成される長方形内の1の個数を数える  
19.       for(int j=y1;j<=y2;j++)  
20.        for(int i=x1;i<=x2;i++)  
21.         if(a[j][i]==1)  
22.          c++;  
23.       // 長方形内のマスが全て1であり  
24.       // 長方形の大きさ(=c)が今までの最大値より大きい場合は更新  
25.       if(c==(x2-x1+1)*(y2-y1+1))  
26.        if(c>res)  
27.         res=c;  
28.      }  
29.     }  
30.    }  
31.   }  
32.   return res;  
33.  }  
34.    
35.  // 動的計画法による実装  
36.  private int count2(int[][] a){  
37.   int m=a[0].length;  
38.   int n=a.length;  
39.   int max=0;  
40.   LinkedList<Point>[][] lists=(LinkedList<Point>[][])new LinkedList[n][m];;  
41.   LinkedList<Point> temp=new LinkedList<Point>();  
42.   
43.   for(int j=0;j<n;j++)  
44.    for(int i=0;i<m;i++)  
45.     lists[j][i]=new LinkedList<Point>();  
46.   
47.   for(int j=0;j<n;j++){  
48.    for(int i=0;i<m;i++){  
49.     if(a[j][i]==0)  
50.      continue;  
51.     int up, left;  
52.     for(up=0;j-up>=0&&a[j-up][i]==1;up++)  
53.      ;  
54.     for(left=0;i-left>=0&&a[j][i-left]==1;left++)  
55.      ;  
56.     // 上隣=0，左隣=0  
57.     if((i==0||a[j][i-1]==0)&&(j==0||a[j-1][i]==0)){  
58.      // (1, 1)  
59.      lists[j][i].add(new Point(1, 1));  
60.     }  
61.     // 上隣=0，左隣=1  
62.     else if(j==0||a[j-1][i]==0){  
63.      // (左方に続く1の個数, 1)  
64.      lists[j][i].add(new Point(left, 1));  
65.     }  
66.     // 上隣=0，左隣=1  
67.     else if(i==0||a[j][i-1]==0){  
68.      // (1, 上方に続く1の個数)  
69.      lists[j][i].add(new Point(1, up));  
70.     }  
71.     // 上隣=1，左隣=1  
72.     else{  
73.      for(Point p:lists[j][i-1])  
74.       lists[j][i].add(new Point(p.x+1, Math.min(p.y, up)));  
75.      for(Point p:lists[j-1][i])  
76.       lists[j][i].add(new Point(Math.min(p.x, left), p.y+1));  
77.     }  
78.   
79.     // 重複要素の削除  
80.     for(Point p:lists[j][i])  
81.      if(!temp.contains(p))  
82.       temp.add(p);  
83.     lists[j][i].clear();  
84.     
85.     // qより大きい長方形が存在したらqをリストに追加しない  
86.     for(Point q:temp){  
87.      for(Point p:temp){  
88.       if(q!=p&&q.x<=p.x&&q.y<=p.y){  
89.        q=null;  
90.        break;  
91.       }  
92.      }  
93.      if(q!=null)  
94.       lists[j][i].add(q);  
95.     }  
96.     temp.clear();  
97.   
98.     for(Point p:lists[j][i])  
99.      max=Math.max(max, p.x*p.y);  
100.    }  
101.   }  
102.   return max;  
103.  }  
104.    
105.  public static void main(String[] args){  
106.   int[][] a;  
107.   a=new int[50][50];  
108.   for(int j=0;j<a.length;j++)  
109.    for(int i=0;i<a[0].length;i++)  
110.     a[j][i]=(int)(Math.random()*2);  
111.   System.out.println("1:"+new Main().count1(a));  
112.   System.out.println("2:"+new Main().count2(a));  
113.  }  
114. }  

import java.util.*;
import java.awt.*;

public class Main{

 // 単純なループによる実装 O(n^6)
 private int count1(int[][] a){
  int res=0;
  int m=a[0].length;
  int n=a.length;
  for(int y1=0;y1<n;y1++){
   for(int x1=0;x1<m;x1++){
    // 始点-(x1, y1)
    for(int y2=y1;y2<n;y2++){
     for(int x2=x1;x2<m;x2++){
      // 終点-(x2, y2)
      int c=0;
      // (x1, y1)-(x2, y2)から構成される長方形内の1の個数を数える
      for(int j=y1;j<=y2;j++)
       for(int i=x1;i<=x2;i++)
        if(a[j][i]==1)
         c++;
      // 長方形内のマスが全て1であり
      // 長方形の大きさ(=c)が今までの最大値より大きい場合は更新
      if(c==(x2-x1+1)*(y2-y1+1))
       if(c>res)
        res=c;
     }
    }
   }
  }
  return res;
 }
 
 // 動的計画法による実装
 private int count2(int[][] a){
  int m=a[0].length;
  int n=a.length;
  int max=0;
  LinkedList<Point>[][] lists=(LinkedList<Point>[][])new LinkedList[n][m];;
  LinkedList<Point> temp=new LinkedList<Point>();

  for(int j=0;j<n;j++)
   for(int i=0;i<m;i++)
    lists[j][i]=new LinkedList<Point>();

  for(int j=0;j<n;j++){
   for(int i=0;i<m;i++){
    if(a[j][i]==0)
     continue;
    int up, left;
    for(up=0;j-up>=0&&a[j-up][i]==1;up++)
     ;
    for(left=0;i-left>=0&&a[j][i-left]==1;left++)
     ;
    // 上隣=0，左隣=0
    if((i==0||a[j][i-1]==0)&&(j==0||a[j-1][i]==0)){
     // (1, 1)
     lists[j][i].add(new Point(1, 1));
    }
    // 上隣=0，左隣=1
    else if(j==0||a[j-1][i]==0){
     // (左方に続く1の個数, 1)
     lists[j][i].add(new Point(left, 1));
    }
    // 上隣=0，左隣=1
    else if(i==0||a[j][i-1]==0){
     // (1, 上方に続く1の個数)
     lists[j][i].add(new Point(1, up));
    }
    // 上隣=1，左隣=1
    else{
     for(Point p:lists[j][i-1])
      lists[j][i].add(new Point(p.x+1, Math.min(p.y, up)));
     for(Point p:lists[j-1][i])
      lists[j][i].add(new Point(Math.min(p.x, left), p.y+1));
    }

    // 重複要素の削除
    for(Point p:lists[j][i])
     if(!temp.contains(p))
      temp.add(p);
    lists[j][i].clear();
  
    // qより大きい長方形が存在したらqをリストに追加しない
    for(Point q:temp){
     for(Point p:temp){
      if(q!=p&&q.x<=p.x&&q.y<=p.y){
       q=null;
       break;
      }
     }
     if(q!=null)
      lists[j][i].add(q);
    }
    temp.clear();

    for(Point p:lists[j][i])
     max=Math.max(max, p.x*p.y);
   }
  }
  return max;
 }
 
 public static void main(String[] args){
  int[][] a;
  a=new int[50][50];
  for(int j=0;j<a.length;j++)
   for(int i=0;i<a[0].length;i++)
    a[j][i]=(int)(Math.random()*2);
  System.out.println("1:"+new Main().count1(a));
  System.out.println("2:"+new Main().count2(a));
 }
}

マージしないでも動作するかな?と思って，マージの実装を外して検証してみましたが，リストに保存する長方形が爆発的に増えた為，メモリが足りませんでした．