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