#include #include #include #include #include #include #include using namespace std; #define REP(i,n) for(int i = 0; i < (int)(n); i++) #define FOR(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i) #define MAX_WIDTH 3 #define MAX_PIECES (MAX_WIDTH*MAX_WIDTH*MAX_WIDTH) typedef unsigned int box_t; /* * P */ struct P { int x, y, z; P(int x=0, int y=0, int z=0) : x(x), y(y), z(z) {} inline int& operator[](int i) { return (i == 0 ? x : i == 1 ? y : z); } inline const int& operator[](int i) const { return (i == 0 ? x : i == 1 ? y : z); } }; inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y, a.z+b.z); } inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y, a.z-b.z); } inline bool operator==(const P& a, const P& b) { return (a.x == b.x && a.y == b.y && a.z == b.z); } inline bool operator!=(const P& a, const P& b) { return !(a == b); } inline bool operator<(const P& a, const P& b) { if (a.x != b.x) return (a.x < b.x); if (a.y != b.y) return (a.y < b.y); if (a.z != b.z) return (a.z < b.z); return false; } ostream& operator<<(ostream& os, const P& p) { os << "(" << p.x << "," << p.y << "," << p.z << ")"; return os; } #define ZERO_MATRIX_INIT {{0,0,0},{0,0,0},{0,0,0}} #define UNIT_MATRIX_INIT {{1,0,0},{0,1,0},{0,0,1}} typedef int matrix_t[3][3]; matrix_t ROT_TABLE[24]; void rotate_axis(matrix_t& mat, int axis) { matrix_t res = ZERO_MATRIX_INIT; matrix_t rot = ZERO_MATRIX_INIT; rot[(axis+0)%3][(axis+0)%3] = 1; rot[(axis+1)%3][(axis+2)%3] = 1; rot[(axis+2)%3][(axis+1)%3] = -1; REP(i, 3) REP(j, 3) REP(k, 3) res[i][j] += rot[i][k] * mat[k][j]; memcpy(mat, res, sizeof(matrix_t)); } void make_rot_table() { matrix_t rot = UNIT_MATRIX_INIT; int rotatePattern = 0; REP(ryz, 6) { REP(rx, 4) { memcpy(ROT_TABLE[rotatePattern++], rot, sizeof(matrix_t)); rotate_axis(rot, 0); } rotate_axis(rot, (ryz % 2 == 0 ? 1 : 2)); } } inline P translate(const P& pieceCell, int rotatePattern, const P& pieceOffset, const P& boxOffset) { const P& pieceDelta = pieceCell - pieceOffset; P boxCell = boxOffset; REP(i, 3) REP(j, 3) boxCell[i] += ROT_TABLE[rotatePattern][i][j] * pieceDelta[j]; return boxCell; } /* * global vars */ int wx, wy, wz, nPieces; vector pieces[MAX_PIECES]; bool pieceUsed[MAX_PIECES]; /* * utilities */ inline bool valid(const P& p) { return (0 <= p.x && p.x < wx && 0 <= p.y && p.y < wy && 0 <= p.z && p.z < wz); } box_t box_from_set(const set

& piece) { box_t box = 0u; FOR(it, piece) { P p = *it; assert(valid(p)); box |= 1u << ((p.z * wy + p.y) * wx + p.x); } return box; } /* * search */ bool solve(box_t current, int depth=0) { if (!current) return true; box_t bit = current & -current; assert(bit); set seen; REP(iPiece, nPieces) { if (pieceUsed[iPiece]) continue; const vector& rotates = pieces[iPiece]; REP(iRotate, rotates.size()) { box_t piece = rotates[iRotate]; if ((piece & bit) != 0 && (current & piece) == piece) { box_t next = current & ~piece; if (seen.insert(next).second) { pieceUsed[iPiece] = true; if (solve(next, depth+1)) return true; pieceUsed[iPiece] = false; } } } } return false; } bool solve() { box_t init = (1u << (wx*wy*wz)) - 1; memset(pieceUsed, 0, sizeof(pieceUsed)); return solve(init); } int main() { make_rot_table(); #ifdef NYA_DEBUG { const P L[] = {P(0,0,0), P(1,0,0), P(1,1,0)}; REP(rotatePattern, 24) { REP(i, 3) { P p = translate(L[i], rotatePattern, P(), P()); cerr << p; } cerr << endl; } cerr << "--" << endl; } #endif // global: int wx, wy, wz, nPieces; while(cin >> wx >> wy >> wz >> nPieces && wx > 0 && wy > 0 && wz > 0 && nPieces > 0) { int nCells = 0; REP(iPiece, nPieces) pieces[iPiece].clear(); REP(iPiece, nPieces) { set< set

> pieceRotations; int pwx, pwy, pwz; cin >> pwx >> pwy >> pwz; set

origPiece; REP(z, pwz) REP(y, pwy) REP(x, pwx) { char c; cin >> ws >> c; if (c == '*') { origPiece.insert(P(x, y, z)); nCells++; } } REP(rotatePattern, 24) { for(int dx = -4; dx <= 4; dx++) { for(int dy = -4; dy <= 4; dy++) { for(int dz = -4; dz <= 4; dz++) { set

piece; FOR(it, origPiece) { P p = translate(*it, rotatePattern, P(), P(dx, dy, dz)); if (!valid(p)) { piece.clear(); break; } piece.insert(p); } if (!piece.empty()) pieceRotations.insert(piece); } } } } FOR(itPiece, pieceRotations) { pieces[iPiece].push_back(box_from_set(*itPiece)); } } #if NYA_DEBUG REP(iPiece, nPieces) { if (iPiece > 0) cerr << "x"; cerr << pieces[iPiece].size(); } cerr << endl; #endif bool res = true; if (nCells != wx*wy*wz) res = false; if (res) res = solve(); cout << (res ? "Yes" : "No") << endl; } return 0; }