SRM 638 Div. 1 Easy: ShadowSculpture

問題

TopCoder Statistics - Problem Statement

解法

• 条件に反さないように立方体を置き、とりあえず立体を作る。
• 全ての立方体が接続されているとは限らないので、接続されている立体ごとに分け、その中に条件を満たすものが存在するかどうか確かめる。

コード

import java.util.ArrayDeque;
import java.util.Deque;

public class ShadowSculpture {

	public String possible(String[] XY, String[] YZ, String[] ZX) {
		int N = XY.length;
		int[][] dir = { { 0, 0, 1 }, { 0, 1, 0 }, { 1, 0, 0 }, { 0, 0, -1 }, { 0, -1, 0 }, { -1, 0, 0 } };

		// [x][y][z]
		boolean[][][] cubes = new boolean[N][N][N];
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				for (int z = 0; z < N; z++) {
					char xy = XY[x].charAt(y);
					char yz = YZ[y].charAt(z);
					char zx = ZX[z].charAt(x);
					if (xy == 'Y' && yz == 'Y' && zx == 'Y') {
						cubes[x][y][z] = true;
					}
				}
			}
		}

		if (!check(N, XY, YZ, ZX, cubes)) {
			return "Impossible";
		}
		if (check(N, XY, YZ, ZX, new boolean[N][N][N])) {
			return "Possible";
		}

		boolean[][][] used = new boolean[N][N][N];
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				for (int z = 0; z < N; z++) {
					if (!used[x][y][z] && cubes[x][y][z]) {
						boolean[][][] testCubes = new boolean[N][N][N];
						testCubes[x][y][z] = true;
						used[x][y][z] = true;
						Deque<Integer[]> deque = new ArrayDeque<>();
						deque.add(new Integer[] { x, y, z });
						while (!deque.isEmpty()) {
							Integer[] p = deque.poll();
							int px = p[0];
							int py = p[1];
							int pz = p[2];
							for (int d = 0; d < 6; d++) {
								int i = px + dir[d][0];
								int j = py + dir[d][1];
								int k = pz + dir[d][2];
								if (i < 0 || j < 0 || k < 0 || i >= N || j >= N || k >= N) {
									continue;
								}
								if (cubes[i][j][k] && !used[i][j][k]) {
									testCubes[i][j][k] = true;
									used[i][j][k] = true;
									deque.add(new Integer[] { i, j, k });
								}
							}
						}
						if (check(N, XY, YZ, ZX, testCubes)) {
							return "Possible";
						}
					}
				}
			}
		}

		return "Impossible";
	}

	boolean check(int N, String[] XY, String[] YZ, String[] ZX, boolean[][][] cubes) {
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				if (XY[x].charAt(y) == 'Y') {
					boolean checked = false;
					for (int z = 0; z < N; z++) {
						if (cubes[x][y][z]) {
							checked = true;
							break;
						}
					}
					if (!checked) {
						return false;
					}
				}
			}
		}

		for (int y = 0; y < N; y++) {
			for (int z = 0; z < N; z++) {
				if (YZ[y].charAt(z) == 'Y') {
					boolean checked = false;
					for (int x = 0; x < N; x++) {
						if (cubes[x][y][z]) {
							checked = true;
							break;
						}
					}
					if (!checked) {
						return false;
					}
				}
			}
		}

		for (int z = 0; z < N; z++) {
			for (int x = 0; x < N; x++) {
				if (ZX[z].charAt(x) == 'Y') {
					boolean checked = false;
					for (int y = 0; y < N; y++) {
						if (cubes[x][y][z]) {
							checked = true;
							break;
						}
					}
					if (!checked) {
						return false;
					}
				}
			}
		}
		return true;
	}
}