SRM 636 Div. 1 Easy: ChocolateDividingEasy

問題

TopCoder Statistics - Problem Statement

解法

どう見ても累積和の問題なんだけど、愚直な全探索で通った（通った）。

コード

public class ChocolateDividingEasy {

	public int findBest(String[] choco) {
		int H = choco.length;
		int W = choco[0].length();
		int[][] chocoMap = new int[H][W];
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				chocoMap[i][j] = Character.getNumericValue(choco[i].charAt(j));
			}
		}

		int max = 0;
		for (int i = 1; i < W - 1; i++) {
			for (int j = i + 1; j < W; j++) {
				for (int i2 = 1; i2 < H - 1; i2++) {
					for (int j2 = i2 + 1; j2 < H; j2++) {

						int min = sumSpace(0, i, 0, i2, chocoMap);
						min = Math.min(sumSpace(i, j, 0, i2, chocoMap), min);
						min = Math.min(sumSpace(j, W, 0, i2, chocoMap), min);
						min = Math.min(sumSpace(0, i, i2, j2, chocoMap), min);
						min = Math.min(sumSpace(i, j, i2, j2, chocoMap), min);
						min = Math.min(sumSpace(j, W, i2, j2, chocoMap), min);
						min = Math.min(sumSpace(0, i, j2, H, chocoMap), min);
						min = Math.min(sumSpace(i, j, j2, H, chocoMap), min);
						min = Math.min(sumSpace(j, W, j2, H, chocoMap), min);

						max = Math.max(max, min);

					}
				}

			}
		}

		return max;
	}

	int sumSpace(int i, int j, int i2, int j2, int[][] map) {
		/*
		 * 横にi<=x<j 縦にi2<=y<j2
		 */

		int ans = 0;
		for (int l = i2; l < j2; l++) {
			for (int k = i; k < j; k++) {
				ans += map[l][k];
			}
		}
		return ans;

	}

}