2010年4月17日土曜日

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

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

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

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

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));
}
}


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

0 件のコメント: