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