Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-13SRM494、SRM498など(DIV1)

SRM494 第一問(250pt) Painting

|  SRM494 第一問(250pt) Painting - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM494 第一問(250pt) Painting - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11310

大きいブラシから塗れるかどうか試していけばおk


public class Painting {
	public int largestBrush(String[] picture) {
		int y = picture.length;
		int x = picture[0].length();
		int[][] pic = new int[y][x];
		int blacks = 0;
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				pic[i][j] = (picture[i].charAt(j) == 'B') ? 0 : 1;
				blacks += 1 - pic[i][j];
			}
		}
		int now = Math.min(x, y);
		int min = 1;

		System.err.println(x + "," + y);

		for (; now >= min ; now--) {
			boolean isok = true;
			boolean[][] painted = new boolean[y][x];
			int nums = 0;
			for (int i = 0; i <= y - now; i++) {
				for (int j = 0; j <= x - now; j++) {
					if (pic[i][j] == 1) {
						continue;
					}
					int n = 0;
					for (int ay = i; ay < i + now; ay++) {
						for (int ax = j; ax < j + now; ax++) {
							n += pic[ay][ax];
						}
					}
					if (n == 0) {
						for (int ay = i; ay < i + now; ay++) {
							for (int ax = j; ax < j + now; ax++) {
								painted[ay][ax] = true;
								nums++;
							}
						}
					}
				}
			}
			isok = true;
			search2:
			for (int i = 0; i < y ; i++) {
				for (int j = 0; j < x ; j++) {
					if (!painted[i][j] && pic[i][j] == 0) {
						isok = false;
						break search2;
					}
				}
			}
			if (isok) {
				return now;
			}
		}
		return 1;
	}
}