POJ1022 Packing Unit 4D Cubes

题目来源：http://poj.org/problem?id=1022

题目大意：

有一些4维的单位体积的立方体盒子，每个立方体有8个面。要用一个大的4为盒子将它们包起来，求最小的大盒子体积。

输入：第一行为测试用例数。每个用例的第一行为单位立方体数目n。接下来的n行每行为一个立方体的信息。每行第一个数字为还立方体的编号，接下来的8个整数分别为对应面相邻的立方体的编号。该面没有邻居则为0.（给出的都是单一刚体。）

输出：最小的能把这个由小4D立方体拼起来的形状的盒子的体积。

---

Sample Input

1
9
1 2 3 4 5 6 7 8 9
2 0 1 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 0 1 0 0 0 0 0
6 0 0 0 0 0 1 0 0
7 0 0 0 0 1 0 0 0
8 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 1 0

Sample Output

81

---

本题题干描述得很复杂，想象起来也有一些抽象，其实很简单，跟3D的情况联系起来想就可以了。3D求包围盒的方法推广至4D即可。

//
//        POJ1022 Packing Unit 4D Cubes
//        Memory: 300K        Time: 16MS
//        Language: C++        Result: Accepted
//

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Cube {
public:
    int x1p, x1n, x2p, x2n, x3p, x3n, x4p, x4n;
};
class Pos {
public:
    int id;
    int x1, x2, x3, x4;
};

int main() {
    int ncase;
    cin >> ncase;
    for (int caseNo = 1; caseNo <= ncase; ++caseNo) {
        int n;
        map<int, Cube> cubes;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int id;
            cin >> id;
            Cube cube;
            cin >> cube.x1p >> cube.x1n >> cube.x2p >> cube.x2n
                >> cube.x3p >> cube.x3n >> cube.x4p >> cube.x4n;
            cubes[id] = cube;
        }
        bool ok = true;
        vector<Pos> solid;
        Pos firstPos;
        firstPos.id = (*cubes.begin()).first;
        firstPos.x1 = firstPos.x2 = firstPos.x3 = firstPos.x4 = 0;
        solid.push_back(firstPos);
        for (map<int, Cube>::iterator itc = cubes.begin(); itc != cubes.end(); ++itc) {
            Cube cube1;
            int id = (*itc).first;
            int x1p = (*itc).second.x1p;
            //x1p
            if (x1p != 0) {
                if (cubes[x1p].x1n != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x1p;
                        pos.x1 = (*its).x1 + 1;
                        pos.x2 = (*its).x2;
                        pos.x3 = (*its).x3;
                        pos.x4 = (*its).x4;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x1p) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }

            //x1n
            int x1n = (*itc).second.x1n;
            if (x1n != 0) {
                if (cubes[x1n].x1p != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x1n;
                        pos.x1 = (*its).x1 - 1;
                        pos.x2 = (*its).x2;
                        pos.x3 = (*its).x3;
                        pos.x4 = (*its).x4;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x1n) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }

            //x2p
            int x2p = (*itc).second.x2p;
            if (x2p != 0) {
                if (cubes[x2p].x2n != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x2p;
                        pos.x1 = (*its).x1;
                        pos.x2 = (*its).x2 + 1;
                        pos.x3 = (*its).x3;
                        pos.x4 = (*its).x4;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x2p) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }
            //x2n
            int x2n = (*itc).second.x2n;
            if (x2n != 0) {
                if (cubes[x2n].x2p != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x2n;
                        pos.x1 = (*its).x1;
                        pos.x2 = (*its).x2 - 1;
                        pos.x3 = (*its).x3;
                        pos.x4 = (*its).x4;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x2n) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }

            //x3p
            int x3p = (*itc).second.x3p;
            if (x3p != 0) {
                if (cubes[x3p].x3n != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x3p;
                        pos.x1 = (*its).x1;
                        pos.x2 = (*its).x2;
                        pos.x3 = (*its).x3 + 1;
                        pos.x4 = (*its).x4;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x3p) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }
            //x3n
            int x3n = (*itc).second.x3n;;
            if (x3n != 0) {
                if (cubes[x3n].x3p != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x3n;
                        pos.x1 = (*its).x1;
                        pos.x2 = (*its).x2;
                        pos.x3 = (*its).x3 - 1;
                        pos.x4 = (*its).x4;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x3n) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }
            //x4p
            int x4p = (*itc).second.x4p;
            if (x4p != 0) {
                if (cubes[x4p].x4n != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x4p;
                        pos.x1 = (*its).x1;
                        pos.x2 = (*its).x2;
                        pos.x3 = (*its).x3;
                        pos.x4 = (*its).x4 + 1;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x4p) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }
            //x4n
            int x4n = (*itc).second.x4n;
            if (x4n != 0) {
                if (cubes[x4n].x4p != id) {
                    ok = false;
                    break;
                }
                bool f = true;
                Pos pos;
                for (vector<Pos>::iterator its = solid.begin(); its != solid.end(); ++its) {
                    if (f == false) break;
                    if ((*its).id == id) {
                        pos.id = x4n;
                        pos.x1 = (*its).x1;
                        pos.x2 = (*its).x2;
                        pos.x3 = (*its).x3;
                        pos.x4 = (*its).x4 - 1;
                        for (vector<Pos>::iterator itr = solid.begin(); itr != solid.end(); ++itr) {
                            if ((*itr).id == x4n) {
                                f = false;
                                break;
                            }
                        }
                    }
                }
                if (f == true) { 
                    solid.push_back(pos);
                }
            }
        }
        if (solid.size() != n) {
            ok = false;
        }
        if (ok == false) {
            cout << "Inconsistent" << endl;
            continue;
        }
        int x1min = 1000;
        int x1max = -1000;
        int x2min = 1000;
        int x2max = -1000;
        int x3min = 1000;
        int x3max = -1000;
        int x4min = 1000;
        int x4max = -1000;
        for (vector<Pos>::iterator it = solid.begin(); it != solid.end(); ++it) {
            if (x1min >(*it).x1) x1min  = (*it).x1;
            if (x1max < (*it).x1) x1max = (*it).x1;
            if (x2min >(*it).x2) x2min  = (*it).x2;
            if (x2max < (*it).x2) x2max = (*it).x2;
            if (x3min >(*it).x3) x3min  = (*it).x3;
            if (x3max < (*it).x3) x3max = (*it).x3;
            if (x4min >(*it).x4) x4min  = (*it).x4;
            if (x4max < (*it).x4) x4max = (*it).x4;
        }
        int vol = (x1max - x1min + 1) * (x2max - x2min + 1) * (x3max - x3min + 1) * (x4max - x4min + 1);
        cout << vol << endl;
    }
    system("pause");
    return 0;
}