雪花是否一样问题

一 原问题链接

SnowflakeSnowSnowflakes - POJ 3349 - Virtual Judgehttps://vjudge.net/problem/POJ-3349

二 输入和输出

1 输入

输入的第1行包含一个整数，表示雪花的数量。接下来的n行，每行都描述一片雪花。每片雪花都包含 6 个整数，表示雪花的花瓣长度。花瓣的长度都将围绕雪花的顺序给出（顺时针或逆时针），但他们可以从 6 个花瓣的任何一个开始。例如，相同的雪花可以被描述为 1 2 3 4 5 6 或 4 3 2 1 6 5

2 输出

如果所有的雪花都不同，则输出“No two snowflakes are alike”，否则输出“Twin snowflakes found.”

三 输入和输出样例

1 输入样例

2

1 2 3 4 5 6

4 3 2 1 6 5

2 输出样例

Twin snowflakes found.

四 分析

本问题可以采用哈希表和 vector 解决，也可以采用哈希表和链式前向星解决。

五 算法设计

1 将雪花的六个花瓣长度求和，然后 mod 一个较大的质数 P，例如 100003 或 100007

2 在哈希表 key 相同的链中查询是否有相同的，如果有则查询是否有相同的，如果有则返回1，否则将关键字添加到 Hash 表中。

3 比较相同时，从顺时针方向和逆时针方向判断

4 以哈希表处理冲突时采用链地址法。采用 vector 或链式前向星都可，但 vector 速度较慢。

六 代码

package poj3349;

import java.util.Scanner;

public class Poj3349 {
    static final int maxn = 100010;
    static final int P = 100007;
    static int head[] = new int[P];
    static int cnt;
    static int snow[][] = new int[maxn][6];
    static int n;
    static node e[] = new node[maxn];

    static {
        cnt = 0;
        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }

    // 将下标 i 添加到值为 val 的链表中
    static void addhash(int val, int i) {
        e[++cnt].to = i;
        e[cnt].next = head[val];
        head[val] = cnt;
    }

    static int cmp(int a, int b) {
        int i, j;
        for (i = 0; i < 6; i++) {
            if (snow[a][0] == snow[b][i]) {
                for (j = 1; j < 6; j++) // 顺时针
                    if (snow[a][j] != snow[b][(j + i) % 6])
                        break;
                if (j == 6) return 1;
                for (j = 1; j < 6; j++)//逆时针
                    if (snow[a][6 - j] != snow[b][(j + i) % 6])
                        break;
                if (j == 6) return 1;
            }
        }
        return 0;
    }

    static boolean find(int i) {
        int key, sum = 0;
        for (int j = 0; j < 6; j++)
            sum += snow[i][j];
        key = sum % P;
        for (int j = head[key]; j != -1; j = e[j].next) {
            if (cmp(i, e[j].to) == 1)
                return true;
        }
        addhash(key, i);
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int flag = 0;
        int sum, key;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 6; j++)
                snow[i][j] = scanner.nextInt();
            if (find(i)) {
                flag = 1;
                break; // 如果多组测试用例，则 continue 继续读入
            }
        }
        if (flag == 1)
            System.out.println("Twin snowflakes found.");
        else
            System.out.println("No two snowflakes are alike.");
        return;
    }
}

class node {
    int to;
    int next;
}

七 测试结果