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