http://acm.pku.edu.cn/JudgeOnline/problem?id=1052

Код:
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
char pattern[3][20][21];
bool cube[20][20][20];
int mark[20][20][20];
int cxy[20][20], cyz[20][20], cxz[20][20];
int ccxy[20][20], ccyz[20][20], ccxz[20][20];
void set_x(int y, int z) {
    for(int x = 0; x < n; ++ x)
        cube[x][y][z] = false;
}
void set_y(int x, int z) {
    for(int y = 0; y < n; ++ y)
        cube[x][y][z] = false;
}
void set_z(int x, int y) {
    for(int z = 0; z < n; ++ z)
        cube[x][y][z] = false;
}
void dfs(int x, int y, int z, int mk) {
    if(x < 0 || x >= n || y < 0 || y >=n || z < 0 || z >= n) return;
    if(! cube[x][y][z] || mark[x][y][z]) return;
    mark[x][y][z] = mk;
    dfs(x + 1, y, z, mk);
    dfs(x - 1, y, z, mk);
    dfs(x, y + 1, z, mk);
    dfs(x, y - 1, z, mk);
    dfs(x, y, z + 1, mk);
    dfs(x, y, z - 1, mk);
}
bool checkcover(int mk) {
    memset(ccxy, 0, sizeof(ccxy));
    memset(ccyz, 0, sizeof(ccyz));
    memset(ccxz, 0, sizeof(ccxz));
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            for(int k = 0; k < n; ++ k)
                if(cube[i][j][k] && mark[i][j][k] == mk) {
                    ccxy[i][j] = 1;
                    ccyz[j][k] = 1;
                    ccxz[i][k] = 1;
                }
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j) {
            if(cxy[i][j] && !ccxy[i][j]) return false;
            if(cyz[i][j] && !ccyz[i][j]) return false;
            if(cxz[i][j] && !ccxz[i][j]) return false;
        }
    return true;
}
bool check() {
    memset(cube, true, sizeof(cube));
    memset(cxy, 0, sizeof(cxy));
    memset(cyz, 0, sizeof(cyz));
    memset(cxz, 0, sizeof(cxz));
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            if(pattern[0][i][j] == '-')
                set_y(i, j);
            else
                cxz[i][j] = 1;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            if(pattern[2][i][j] == '-')
                set_z(i, j);
            else
                cxy[i][j] = 1;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            if(pattern[1][i][j] == '-')
                set_x(i, j);
            else
                cyz[i][j] = 1;
    int conn = 0;
    memset(mark, 0, sizeof(mark));
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            for(int k = 0; k < n; ++ k)
                if(cube[i][j][k] && ! mark[i][j][k]) {
                    dfs(i, j, k, ++ conn);
                    if(checkcover(conn)) return true;
                }
    return false;
}
void trans(int i) {
    int tmp[20][20];
    for(int j = 0; j < n; ++ j)
        for(int k = 0; k < n; ++ k)
            tmp[j][k] = pattern[i][k][j];
    for(int j = 0; j < n; ++ j)
        for(int k = 0; k < n; ++ k)
            pattern[i][j][k] = tmp[j][k];
}
bool sol(int i) {
    if(i == 3) return check();
    for(int j = 0; j < 4; ++ j) {
        if(sol(i + 1)) return true;
        trans(i);
    }
    return false;
}
int main() {
    int cases = 0;
    while(scanf("%d", &n), n) {
        for(int i = 0; i < 3; ++ i)
            for(int j = 0; j < n; ++ j)
                scanf("%s", pattern[i][j]);
        printf("Data set %d: %s\n", ++ cases, sol(0) ? "Valid set of patterns" : "Impossible combination");
    }
}