2014
01-10

# UVa-197-Cube(立方体)-计算几何

Time limit: 30.000 seconds

## Problem问题

There was once a 3 by 3 by 3 cube built of 27 smaller cubes. It has fallen apart into seven pieces:

Figure 1: The seven pieces that once formed a cube

The seven pieces can be assembled in many ways to again form the cube. Figure 2 shows one of these possibilities. The first square stands for the front plane, the next one for the middle plane and the last one for the back plane of the cube. The letters in the cells stand for the name of piece filling out the corresponding space in the cube. The name of the seven pieces can be found in figure 1.

Figure 2: Two possibilities of assembling the cube

You are to write a program that outputs all possibilities of assembling the cube but suppress solutions that are mere rotations of another solution.

Hint: Piece a is the only part that, by rotation and translation, cannot be transformed into itself. In order to avoid solutions that are mere rotations of an already found solution, you may restrict transformations of piece a to translations.

## Input输入

The input file has several test cases. Each test case indicates the initial position of piece a’. You can translate it, but you mustn’t rotate it.

## Output输出

For each solution found, your program should output a line containing the solution as a string. The string is a linearized form of the cube. Each letter stands for the piece filling out the corresponding space in the cube. It is linearized as follows:

• The string consists of substrings representing the front, middle and back plane.
• 字符串由三个子串构成，分别代表：前平面、中平面和后平面。
• Each substring consists of substrings representing the top, middle and bottom row.
• 每个子串又由三个子串构成，分别代表：顶行，中行和底行。
• Each row substring consists of letters representing the left, middle and right cell.
• 每行的子串又由三个字母构成，分别为左格，中格和右格。

The solutions in figure 2 would be represented like this:

It is very important that your program uses the naming convention given in figure 1 and linearizes the cube as explained above.

Print a blank line after each test case.

Figure 3: Positions of the cells in the string

Figure 3 again shows how the cells of the cube are linearized.

aa.a..a………………..
………a..a..aa……….

## Analysis分析

1: (0, 2, 2),  2: (1, 2, 2),  3: (2, 2, 2),
4: (0, 1, 2),  5: (1, 1, 2),  6: (2, 1, 2),
7: (0, 0, 2),  8: (1, 0, 2),  9: (2, 0, 2),
10: (0, 2, 1), 11: (1, 2, 1), 12: (2, 2, 1),
13: (0, 1, 1), 14: (1, 1, 1), 15: (2, 1, 1),
16: (0, 0, 1), 17: (1, 0, 1), 18: (2, 0, 1),
19: (0, 2, 1), 20: (1, 2, 1), 21: (2, 2, 1),
22: (0, 1, 1), 23: (1, 1, 1), 24: (2, 1, 1),
25: (0, 0, 1), 26: (1, 0, 1), 27: (2, 0, 1),

1. 你的小方块编号要与题目一致，注意建立正确的坐标系；
2. 题目给的输出范例是错的，对于每一个输入，你的输出结果字符串要进行排序；
3. 对于每一个输入的a的构形，你不能旋转，但一定要计算a的每一种可行平移的解，再汇总；
4. 仔细优化递归函数，否则可能TLE；
5. 先考虑设计完善的数据结构和代码结构，以免调试时找不着北。

## Solution解答

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <memory.h>

struct POINT3		// 定义每个方块的坐标的结构体
{
int x;
int y;
int z;
};
typedef std::vector<POINT3> COORDS;		// 类型定义，表示图中7个piece的坐标
typedef unsigned long FORMMASK;			// 类型定义，表示每一个piece经过旋转、偏移之后产生的一种构型的掩码
typedef std::vector<int> MATRIX;		// 类型定义，表示矩阵
typedef std::vector<MATRIX> ROTMATS;	// 类型定义，表示矩阵的集合
ALLPIECEFORMS allPieceForms;			// 全局变量，存储所有piece经过旋转、偏移后的掩码
ALLPIECEFORMS result;					// 全局变量，存储最终的结果
ROTMATS rotMats;						// 全局变量，存储旋转矩阵

// 单位矩阵分别绕X、Y、Z轴旋转0°、90°、180°、270°后对应的矩阵
int rotateMatX[][9] = {
{1, 0, 0, 0, 1, 0, 0, 0, 1},
{1, 0, 0, 0, 0, -1, 0, 1, 0},
{1, 0, 0, 0, -1, 0, 0, 0, -1},
{1, 0, 0, 0, 0, 1, 0, -1, 0}
};
int rotateMatY[][9] = {
{1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, -1, 0, 0},
{-1, 0, 0, 0, 1, 0, 0, 0, -1},
{0, 0, -1, 0, 1, 0, 1, 0, 0}
};
int rotateMatZ[][9] = {
{1, 0, 0, 0, 1, 0, 0, 0, 1},
{0, -1, 0, 1, 0, 0, 0, 0, 1},
{-1, 0, 0, 0, -1, 0, 0, 0, 1},
{0, 1, 0, -1, 0, 0, 0, 0, 1}
};
// 题目图中7中piece相应的空间坐标，顺序为a，f，g，e，c，d，b，以左下角为原点(0,0,0)
POINT3 pieces[][4] = {
{{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 2, 0}},
{{0, 0, 0}, {1, 0, 0}, {1, 0, 1}, {1, 1, 1}},
{{0, 0, 0}, {1, 0, 0}, {1, 0, 1}, {0, 1, 0}},
{{0, 0, 0}, {0, 0, 1}, {1, 0, 1}, {0, 1, 1}},
{{0, 1, 0}, {1, 0, 0}, {1, 1, 0}, {1, 2, 0}},
{{0, 0, 0}, {0, 0, 1}, {1, 0, 1}, {1, 0, 2}},
{{0, 0, 0}, {1, 0, 0}, {0, 0, 1},}
};
char nameMap[] = {'a', 'f', 'g', 'e', 'c', 'd', 'b'};
// 直角坐标系与题目坐标系的位置编号对应表
char posMap[] = {24, 25, 26, 21, 22, 23, 18, 19, 20, 15, 16, 17, 12, 13, 14, 9, 10, 11, 6, 7, 8, 3, 4, 5, 0, 1, 2};

bool operator < (const POINT3 &p1, const POINT3 &p2)
{
return (p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y) ||
(p1.x == p2.x && p1.y == p2.y && p1.z < p2.z));
}

bool operator == (const POINT3 &p1, const POINT3 &p2)
{
return (p1.x == p2.x && p1.y == p2.y && p1.z == p2.z);
}
// 计算矩阵乘法，输入两个矩阵pM1，pM2，并输入第一个矩阵的行数，第二个矩阵的列数以及矩阵的大小，输出矩阵相乘的结果pR。
void MatMul(int *pM1, int *pM2, int r1, int c2, int n, int *pR)
{
for (int i = 0; i < r1; ++i) {
for (int j = 0; j < c2; ++j) {
pR[i * c2 + j] = 0;
for (int k = 0; k < n; ++k)
pR[i * c2 + j] += pM1[i * r1 + k] * pM2[k * c2 + j];
}
}
}
// 求坐标的相反数
POINT3 Inverse(POINT3 &coord)
{
coord.x = -coord.x;
coord.y = -coord.y;
coord.z = -coord.z;
return coord;
}
// 找出一个piece中坐标最大的点和坐标最小的点
void Bound(const COORDS &coords, POINT3 &min, POINT3 &max)
{
min = max = coords[0];
for (size_t i = 1; i < coords.size(); ++i) {
if (coords[i].x < min.x) min.x = coords[i].x;
if (coords[i].x > max.x) max.x = coords[i].x;
if (coords[i].y < min.y) min.y = coords[i].y;
if (coords[i].y > max.y) max.y = coords[i].y;
if (coords[i].z < min.z) min.z = coords[i].z;
if (coords[i].z > max.z) max.z = coords[i].z;
}
}
// 根据piece中坐标的最小值，标记一个piece进行偏移转换时能偏移的最大位置
void PieceSize(const COORDS &coords, POINT3 &size)
{
POINT3 minCoord;
Bound(coords, minCoord, size);
size.x -= minCoord.x;
size.y -= minCoord.y;
size.z -= minCoord.z;
}
// piece的偏移转换
void Translate(COORDS &coords, const POINT3 &dist)
{
for (size_t i = 0; i < coords.size(); ++i) {
coords[i].x += dist.x;
coords[i].y += dist.y;
coords[i].z += dist.z;
}
}
// 计算一个piece的掩码，根据piece中各个方块的位置坐标计算其在最终的结果序列中出现的位置。
{
for (COORDS::iterator j = coords.begin(); j != coords.end(); ++j) {
ulMask |= (1 << (j->x + j->y * 3 + j->z * 9));
}
}
// 旋转、偏移转换3×3×3方块，forms记录给定piece的所有构型掩码
void ExpandForms(const POINT3 *pPiece, int n, VECFORMMASK &forms)
{
// 从数据指针构造坐标数组，并排序
COORDS coords(pPiece, pPiece + n), rotCoords(n);
POINT3 minCoord, size;
std::sort(coords.begin(), coords.end());

// rots记录给定piece的所有旋转
std::vector<COORDS> rots;

// 求出所有的旋转构型，包括不旋转的原构型（单位阵），每一个旋转构型最多有24个不同构型
for (ROTMATS::iterator i = rotMats.begin(); i != rotMats.end(); ++i) {
for (int j = 0; j < n; ++j) {
MatMul(i->data(), (int*)&coords[j], 3, 1, 3, (int*)&rotCoords[j]);
}
// 规格化每一种旋转构型，使旋转后的方块仍以左下角的小方块为原点
Bound(rotCoords, minCoord, size);
Translate(rotCoords, Inverse(minCoord));
std::sort(rotCoords.begin(), rotCoords.end());
rots.push_back(rotCoords);
}
// 去除重复的旋转构型
std::sort(rots.begin(), rots.end());
rots.erase(std::unique(rots.begin(), rots.end()), rots.end());
size_t nRotCnt = rots.size();
// 将每一种旋转构型偏移，产生新的偏移构型，每一个piece均有6个偏移构型
for (size_t i = 0; i != nRotCnt; ++i) {
PieceSize(rots[i], size);
for (minCoord.x = 0; minCoord.x < 3 - size.x; ++minCoord.x) {
for (minCoord.y = 0; minCoord.y < 3 - size.y; ++minCoord.y) {
for (minCoord.z = 0; minCoord.z < 3 - size.z; ++minCoord.z) {
if (minCoord.x != 0 || minCoord.y != 0 || minCoord.z != 0) {
rots.push_back(rots[i]);
Translate(rots.back(), minCoord);
}
}
}
}
}
// 计算相应构型的掩码
for (std::vector<COORDS>::iterator i = rots.begin(); i != rots.end(); ++i) {
}
}
// 递归的查找题中的7种piece的组合结果，path中记录每一种组合的所有piece的掩码
{
// 递归结束条件，每一种组合的掩码完全填充
if (nCube == 0x07ffffff) {
result.push_back(path);
return;
}
size_t nFormCnt = curForm->size();
for (size_t i = 0; i < nFormCnt; ++i) {
// 判断当前的掩码中是否有某一piece的掩码，若没有，则修改当前掩码，并在path中记录piece
if (((~pForms[i]) & nCube) == nCube) {
unsigned long nTmpCube = nCube | pForms[i];
path.push_back(pForms[i]);
FillCube(curForm + 1, nTmpCube, path);
path.pop_back();
}
}
}

int main(void)
{
// 计算旋转矩阵，共计24种旋转情况，如：绕XY轴旋转90°，绕XZ轴旋转180°等
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 4; ++k) {
int tmp1[9];
rotMats.push_back(std::vector<int>(9));
MatMul(rotateMatY[j], rotateMatZ[k], 3, 3, 3, tmp1);
MatMul(rotateMatX[i], tmp1, 3, 3, 3, rotMats.back().data());
}
}
}
std::sort(rotMats.begin(), rotMats.end());
rotMats.erase(std::unique(rotMats.begin(), rotMats.end()), rotMats.end());

// 初始化piece的所有旋转和偏移的构型
allPieceForms.resize(7);
for (int i = 0; i < 7; ++i) {
ExpandForms(pieces[i], 4 - (i / 6), allPieceForms[i]);
}

for (std::string strLine; getline(std::cin, strLine) && !strLine.empty(); )
{
// 计算读入的数据中a的位置
COORDS inputA;
result.clear();
for (std::string::iterator i = strLine.begin(); i != strLine.end(); ++i) {
if (*i == 'a') {
int nIdx = i - strLine.begin();
POINT3 tmp = {nIdx % 3, 2 - (nIdx % 9) / 3, 2 - nIdx / 9};
inputA.push_back(tmp);
}
}
// 将读入的pieceA的坐标规格化为空间直角坐标系并建立相应的掩码
POINT3 minCoord, tmp;
Bound(inputA, minCoord, tmp);
Translate(inputA, Inverse(minCoord));
std::sort(inputA.begin(), inputA.end());
// 查找读入的pieceA转化到空间直角坐标系后相应的构型
int nRot = std::find(allPieceForms[0].begin(), allPieceForms[0].end(),
// 计算pieceA对应的所有组合
FillCube(allPieceForms.begin() + 1, fixedA, vfm);
// 计算pieceA经过偏移处理后的所有组合
for (int i = nRot * 5 + 24; i < (nRot + 1) * 5 + 24; ++i) {
fixedA = allPieceForms[0][i];
FillCube(allPieceForms.begin() + 1, fixedA, vfm);
}
// 将所有掩码的组合转换为输出形式的字符串
std::vector<std::string> outStrs;
for (ALLPIECEFORMS::iterator i = result.begin(); i != result.end(); ++i) {
std::string str;
str.resize(27);
for (size_t j = 0; j < i->size(); ++j) {
for (size_t k = 0; k < 27; ++k) {
if (mask & (1 << posMap[k])) {
//判断条件中posMap[k]为将空间直角坐标系对应到题中坐标系的位置，调整输出字符串的顺序，与题中输出要求相符
str[k] = nameMap[j];
}
}
}
outStrs.push_back(str);
}
std::sort(outStrs.begin(), outStrs.end());
for (std::vector<std::string>::iterator i = outStrs.begin(); i != outStrs.end(); ++i) {
std::cout << *i << std::endl;
}
std::cout << std::endl;
}

return 0;
}`

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。

2. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？