uva 12326 & hdu 4092 - Yummy Triangular Pizza(哈希+击表)

uva 12326 & hdu 4092 - Yummy Triangular Pizza(哈希+打表)

题目链接：uva 12326 &hdu 4092 Yummy Triangular Pizza

题目大意：给出n，表示用n个正三角形去组成图形，问可以组成多少种不同的三角形，旋转，镜像，都算同一种。

解题思路：参考别人的思路，很巧妙，主要就是建立三维坐标轴。

正立三角形x+y+z = 0
倒立三角形x+y+z ≠ 0

这样从初始装态为0 0 0的三角形开始逐个添加，每次进行旋转镜像，判断是否有没有重复。
每次判断重复的时候，枚举图形中的一个三角做为原点处理，生成hash值，以为n为多位16，所以x，y，z的范围不会大过8.

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;
const int maxn = 16;

struct Trian {
    int x, y, z;
    Trian () {};
    Trian (int x, int y, int z) {
        this->x = x;
        this->y = y;
        this->z = z;
    }

    Trian add (int type) {
        int mv = (x+y+z == 0 ? 1 : -1);
        if (type == 0)
            return Trian(x, y+mv, z+mv);
        else if (type == 1)
            return Trian(x+mv, y, z+mv);
        else
            return Trian(x+mv, y+mv, z);
    }

    void rotate () {
        int tmp = x;
        x = y;
        y = z;
        z = tmp;
    }

    void overturn () {
        x = 1 - x;
        y = 1 - y;
        z = -z;
    }

    void move (int x, int y, int z) {
        this->x += x;
        this->y += y;
        this->z += z;
    }
};

bool operator == (const Trian& a, const Trian& b) {
    return a.x == b.x && a.y == b.y && a.z == b.z;
}

bool operator < (const Trian& a, const Trian& b) {
    if (a.x != b.x)
        return a.x < b.x;
    else if (a.y != b.y)
        return a.y < b.y;
    else
        return a.z < b.z;
}

struct Hash {
    int cnt, key[maxn+5];
};

bool operator < (const Hash& a, const Hash& b) {
    if (a.cnt != b.cnt)
        return a.cnt < b.cnt;
    for (int i = 0; i < a.cnt; i++)
        if (a.key[i] != b.key[i])
            return a.key[i] < b.key[i];
    return false;
}

struct Pizz {
    int cnt;
    Trian arr[maxn+5];
    Pizz () { cnt = 0; }

    bool add (const Trian& u) {

        for (int i = 0; i < cnt; i++)
            if (arr[i] == u)
                return false;
        arr[cnt++] = u;
        return true;
    }

    void remove () { cnt--; }

    Hash getKey () {
        Hash u;
        u.cnt = cnt;

        for (int i = 0; i < cnt; i++) {
            u.key[i] = arr[i].x + 8;
            u.key[i] <<= 4;
            u.key[i] += arr[i].y + 8;
            u.key[i] <<= 4;
            u.key[i] += arr[i].z + 8;
        }
        return u;
    }
};

set<Hash> vis;
int ans[maxn+5] = {0};

bool find (Pizz v) {
    for (int i = 0; i < 3; i++) {
        sort(v.arr, v.arr+v.cnt);
        if (vis.find(v.getKey()) != vis.end())
            return true;

        for (int j = 0; j < v.cnt; j++)
            v.arr[j].rotate();
    }
    return false;
}

bool search (Pizz u) {
    for (int i = 0; i < u.cnt; i++) {
        int x = u.arr[i].x;
        int y = u.arr[i].y;
        int z = u.arr[i].z;

        Pizz v = u;
        if (x + y + z == 0) {

            for (int j = 0; j < v.cnt; j++)
                v.arr[j].move(-x, -y, -z);

            if (find(v))
                return true;
        } else {

            for (int j = 0; j < v.cnt; j++) {
                v.arr[j].overturn();
                v.arr[j].move(x-1, y-1, z);
            }

            if (find(v))
                return true;
        }
    }
    return false;
}

void insert (Pizz u) {
    for (int i = 0; i < 3; i++) {
        sort(u.arr, u.arr+u.cnt);    
        vis.insert(u.getKey());

        for (int j = 0; j < u.cnt; j++)
            u.arr[j].rotate();
    }
}

void dfs (Pizz u) {
    if (u.cnt == maxn+1)
        return;

    if (search(u))
        return;

    insert(u);
    ans[u.cnt]++;

    for (int i = 0; i < u.cnt; i++) {
        for (int j = 0; j < 3; j++) {
            Trian v = u.arr[i].add(j);
            if (u.add(v)) {
                dfs(u);
                u.remove();
            }
        }
    }
}
int rec[maxn+5] = {0, 1, 1, 1, 4, 6, 19, 43, 120, 307, 866, 2336, 6588, 18373, 52119, 147700, 422016};

int main () {
    /*
    Pizz u;
    u.add(Trian(0, 0, 0));
    dfs(u);

    for (int i = 0; i <= maxn; i++)
        printf("%d\n", ans[i]);
    */

    int cas, n;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        scanf("%d", &n);
        printf("Case #%d: %d\n", i, rec[n]);
    }
    return 0;
}