1255 Floors

1255 -- Floors
アルゴリズムよりもComparatorの定義の仕方に議論が集中した。

フロアを2つに分けられるかどうかの判定方法が人それぞれだったけれど、基本的には同じアルゴリズムだった。
僕が書いたコードは下のやつ。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		
		int floorNum=s.nextInt();
		for(;floorNum-->0;){
			int width=s.nextInt();
			int height=s.nextInt();
			int[][] floors=new int[s.nextInt()][];
			for(int j=0;j<floors.length;++j) {
				int[] floor=new int[4];
				for(int i=0;i<floor.length;++i) {
					floor[i]=s.nextInt();
				}
				floors[j]=floor;
			}
			System.out.println(getMaxSquare(width, height, floors, 0, floors.length));
		}
	}

	public static int getMaxSquare(int width, int height, int[][] floors, int start, int end){
		
		if( start == end - 1 ) {
			return width * height;
		}
		
		boolean isCut = false;
		
		int fw = 0;
		int fh = 0;

		for(int i=start; i<end; ++i) {
			int wsum = floors[i][2] - floors[i][0];
			int hsum = floors[i][3] - floors[i][1];
			for(int j=start; j<end; ++j ){
				if( i == j ) continue;
				if ( floors[i][2] == floors[j][2]) {
					hsum = hsum + floors[j][3] - floors[j][1];
				}
				
				if ( floors[i][3] == floors[j][3] ) {
					wsum = wsum + floors[j][2] - floors[j][0];
				}
			}
						
			if( wsum == width && floors[i][3] != height ) {
				isCut = true;
				fw = wsum;
				fh = floors[i][3];
				break;
			} 
			
			if( hsum == height && floors[i][2] != width ) {
				isCut = true;
				fw = floors[i][2];
				fh = hsum;
				break;
			}
		}
		
		if( !isCut ) return width * height;
		
		class xrCmp implements Comparator<int[]> {
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		}
		
		class yrCmp implements Comparator<int[]> {
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		}
		
		if( fw == width ) {
			Arrays.sort(floors, start, end, new yrCmp());
			
			int division=start;
			for(int i=start;i<end;++i) {
				if(floors[i][1] >= fh) {
					floors[i][1] -= fh;
					floors[i][3] -= fh;
				} else {
					division = i;
				}
			}
			
			return Math.max(
					getMaxSquare(width, fh, floors, start, division + 1),
					getMaxSquare(width, height - fh, floors, division + 1, end));
			
		} else {
			Arrays.sort(floors, start, end, new xrCmp());
			
			int division=start;
			for(int i=start;i<end;++i) {
				if(floors[i][0] >= fw) {
					floors[i][0] -= fw;
					floors[i][2] -= fw;
				} else {
					division = i;
				}
			}
			
			return Math.max(
					getMaxSquare(fw, height, floors, start, division + 1),
					getMaxSquare(width - fw, height, floors, division + 1, end));
		}
	}
}