ACM/ICPC 2001 国内予選

問題A : Get A Rectangular Field

ACM/ICPC Japan Domestic 2001 Problem A

突貫工事。動的計画法の問題です。場合分けがめんどい。

import java.io.*;
import java.util.*;

public class GetARectangularField {

  public static void main(String[] args) {
    try {
      Scanner in = new Scanner(new File("A.in"));
      
      // map数の読み込み
      int m = in.nextInt();
      
      // map数分ループ
      for (; m > 0; m--) {
        // map作成
        Place[][] map = new Place[5][5];
        for (int i = 0; i < 5; i++) {
          for (int j = 0; j < 5; j++)
            map[i][j] = new Place(in.nextInt());
        }
        
        // 最大長方形の面積
        int maxArea = 0;
        
        for (int i = 0; i < 5; i++) {
          for (int j = 0; j < 5; j++) {
            // 現在点が0なら無視
            if (map[i][j].landType == 0)
              continue;
            
            // 以下、現在点が1

            // 左と上のマスが範囲内の場合
            if (i - 1 >= 0 && j - 1 >= 0) {
              // 左が0、上が0の場合
              if (map[i][j - 1].landType == 0 && map[i - 1][j].landType == 0) {
                map[i][j].memo.add(new Memo(1, 1));
                maxArea = Math.max(1, maxArea);
              }
              
              // 左が1、上が0の場合
              if (map[i][j - 1].landType == 1 && map[i - 1][j].landType == 0) {
                for (int k = 0; k < map[i][j - 1].memo.size(); k++) {
                  Memo temp = new Memo(map[i][j - 1].memo.get(k).x + 1, 1);
                  map[i][j].memo.add(temp);
                  maxArea = Math.max(temp.x * temp.y, maxArea);
                }
              }
              
              // 左が0、上が1の場合
              if (map[i][j - 1].landType == 0 && map[i - 1][j].landType == 1) {
                for (int k = 0; k < map[i - 1][j].memo.size(); k++) {
                  Memo temp = new Memo(1, map[i - 1][j].memo.get(k).y + 1);
                  map[i][j].memo.add(temp);
                  maxArea = Math.max(temp.x * temp.y, maxArea);
                }
              }
              
              // 左が1、上が1の場合
              if (map[i][j - 1].landType == 1 && map[i - 1][j].landType == 1) {
                // 左のメモを参照して、現在点のメモを作成
                int maxUp = 0;
                for (int k = 0; k < map[i - 1][j].memo.size(); k++)
                  maxUp = Math.max(map[i - 1][j].memo.get(k).y, maxUp);
                for (int k = 0; k < map[i][j - 1].memo.size(); k++) {
                  Memo temp = new Memo(map[i][j - 1].memo.get(k).x + 1, Math.min(map[i][j - 1].memo.get(k).y, maxUp + 1));
                  map[i][j].memo.add(temp);
                  maxArea = Math.max(temp.x * temp.y, maxArea);
                }
                // 上のメモを参照して、現在点のメモを作成
                int maxLeft = 0;
                for (int k = 0; k < map[i][j - 1].memo.size(); k++)
                  maxLeft = Math.max(map[i][j - 1].memo.get(k).x, maxLeft);
                for (int k = 0; k < map[i - 1][j].memo.size(); k++) {
                  Memo temp = new Memo(Math.min(map[i - 1][j].memo.get(k).x, maxLeft + 1), map[i - 1][j].memo.get(k).y + 1);
                  map[i][j].memo.add(temp);
                  maxArea = Math.max(temp.x * temp.y, maxArea);
                }
              }
            }
            
            // 左のマスが範囲外で、上のマスが範囲内の場合
            if (j - 1 < 0 && i - 1 >= 0) {
              // 上のマスが1のとき
              if (map[i - 1][j].landType == 1) {
                for (int k = 0; k < map[i - 1][j].memo.size(); k++) {
                  Memo temp = new Memo(1, map[i - 1][j].memo.get(k).y + 1);
                  map[i][j].memo.add(temp);
                  maxArea = Math.max(temp.x * temp.y, maxArea);
                }
              }
              // 上のマスが0のとき
              else if (map[i - 1][j].landType == 0) {
                Memo temp = new Memo(1, 1);
                map[i][j].memo.add(temp);
                maxArea = Math.max(1, maxArea);
              }
              
            }
            
            // 左のマスが範囲内で、上のマスが範囲外の場合
            if (j - 1 >= 0 && i - 1 < 0) {
              // 左のマスが1のとき
              if (map[i][j - 1].landType == 1) {
                for (int k = 0; k < map[i][j - 1].memo.size(); k++) {
                  Memo temp = new Memo(map[i][j - 1].memo.get(k).x + 1, 1);
                  map[i][j].memo.add(temp);
                  maxArea = Math.max(temp.x * temp.y, maxArea);
                }
              }
              // 左のマスが0のとき
              else if (map[i][j - 1].landType == 0) {
                Memo temp = new Memo(1, 1);
                map[i][j].memo.add(temp);
                maxArea = Math.max(1, maxArea);
              }
            }
            
            // 左のマスも上のマスも範囲外の場合
            if (j - 1 < 0 && i - 1 < 0) {
              Memo temp = new Memo(1, 1);
              map[i][j].memo.add(temp);
              maxArea = Math.max(1, maxArea);
            }
          }
        }
        
        System.out.println(maxArea);
      }

    } catch(Exception e) {
      e.printStackTrace();
    }
  }

}

class Place {
  int landType;
  ArrayList<Memo> memo = new ArrayList<Memo>();
  
  Place(int landType) {
    this.landType = landType;
  }
}

class Memo {
  int x;
  int y;
  
  Memo(int x, int y) {
    this.x = x;
    this.y = y;
  }
}