SRM 655 Div. 1 Easy: BichromePainting (AC)

解法

X-Ray Screening System | Aizu Online Judge

解法はAOJ 2002と同じ。必ず1番上に隠れていない正方形があるはずなので、それを取り除く。するとまた一番上に正方形が出てくるはずなので取り除く… というのを繰り返し、取り除ける正方形が無くなった時にボード上に残っているものがあれば "Impossible" を返す。

コード

public class BichromePainting {

	public String isThatPossible(String[] board, int k) {
		int N = board.length;
		char[][] map = new char[N][];
		for (int i = 0; i < map.length; i++) {
			map[i] = board[i].toCharArray();
		}

		while (true) {
			// 正方形が見つかったかどうか
			boolean found = false;

			for (int i = 0; i <= N - k; i++) {
				for (int j = 0; j <= N - k; j++) {
					boolean black = false;
					boolean white = false;

					for (int p = i; p < i + k; p++) {
						for (int q = j; q < j + k; q++) {
							if (map[p][q] == 'B') {
								black = true;
							}
							if (map[p][q] == 'W') {
								white = true;
							}
						}
					}
					if (black != white) {
						found = true;
						for (int p = i; p < i + k; p++) {
							for (int q = j; q < j + k; q++) {
								map[p][q] = '?';
							}
						}
					}
				}
			}
			if (!found) {
				break;
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != '?') {
					return "Impossible";
				}
			}
		}
		return "Possible";

	}

}