POJ-3349-Snowflake Snow Snowflakes-hash

第一次用hash解题。
这道题早就想A了，只是觉得挺难，便一直放下。今天本想下定决心自己做出来的，没想到自己写的代码一直WA，相当恼人。最后参考了网友的程序，虽要3454MS，但总算也过了。
解决此题的关键有二：
1. 构造hash表，应能想到hash表项存储的是雪花数组下标。其实hash表项设定为vector挺好用的，当hash表项存储的元素增加时，直接push_back即可，vector这个动态数组很好用;
2. 判断两个雪花是否相同，注意到顺时针和逆时针即可。
嗯，好了，上代码，你们看吧，注释挺详细的了。

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;

const int MAX_SIZE = 100005; //最大的雪花数
const int MOD_VAL = 90001; //hash函数，取余的数

int snow[MAX_SIZE][6]; //存储雪花信息
vector<int> hash[MOD_VAL]; //hash表，表中存储的是snow数组的下标

/*判断雪花a与雪花b是否同样
 *输入：两个雪花在snow数组的下标
 *输出：true or false
 */
bool isSame(int a, int b) {
    for(int i=0;i<6;i++)
    {
        if(/*顺时针方向*/
          (snow[a][0] == snow[b][i] &&
           snow[a][1] == snow[b][(i+1)%6] &&
           snow[a][2] == snow[b][(i+2)%6] &&
           snow[a][3] == snow[b][(i+3)%6] &&
           snow[a][4] == snow[b][(i+4)%6] &&
           snow[a][5] == snow[b][(i+5)%6])

           ||
            /*逆时针方向*/
           (snow[a][0] == snow[b][i] &&
            snow[a][1] == snow[b][(i+5)%6] &&
            snow[a][2] == snow[b][(i+4)%6] &&
            snow[a][3] == snow[b][(i+3)%6] &&
            snow[a][4] == snow[b][(i+2)%6] &&
            snow[a][5] == snow[b][(i+1)%6])
           )

        return true;
    }

    return false;
}

int main()
{
    /*处理输入*/
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 6; j++) {
            scanf("%d", &snow[i][j]);
        }
    }

    /*分别处理这n个雪花，判断有没两个雪花是相同的*/
    int sum, key;
    for(int i = 0; i < n; i++) {
        /*求出雪花六个花瓣的和*/
        sum = 0;
        for(int j = 0; j < 6; j++) {
            sum += snow[i][j];
        }

        key = sum % MOD_VAL; //求出key

        /*判断在hash表中hash[key]存储的雪花是否与雪花i相同*/
        for(vector<int>::size_type j = 0; j < hash[key].size(); j++) {
            /*若相同，则直接输出，并结束程序*/
            if(isSame(hash[key][j], i)) {
                printf("%s/n", "Twin snowflakes found.");
                exit(0);
            }
        }
        /*若key相同的雪花没有一个与雪花i相同*/
        hash[key].push_back(i);
    }

    /*若都不相同*/
    printf("%s/n", "No two snowflakes are alike.");

    return 0;
}