AOJ1114 Get a Rectangular Field

問題リンク Get a Rectangular Field

• 概要

5*5のマスに0か1が書かれている。1のみを含む長方形を作るとき、できる最大面積を答えよ。

• 解法

問題のサイズが非常に小さいので、(i, j)を左上のマスとして幅w, 高さhの長方形が作れるかというのを全て試すことができます。
※より厳しい条件の問題がAOJ0116にあります

• ソース

import java.util.Scanner;

//Get a Rectangular Field
public class AOJ1114 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			int[][] a = new int[5][5];
			for(int i=0;i<5;i++)for(int j=0;j<5;j++)a[i][j]=sc.nextInt();
			int max = 0;
			for(int i=0;i<5;i++){
				for(int j=0;j<5;j++){
					for(int h=i;h<5;h++){
						for(int w=j;w<5;w++){
							boolean f = true;
							for(int n=i;n<=h;n++){
								for(int m=j;m<=w;m++){
									if(a[n][m]==0){
										f = false;break;
									}
								}
							}
							if(f)max = Math.max(max, (h-i+1)*(w-j+1));
						}
					}
				}
			}
			System.out.println(max);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1114().run();
	}
}