Is the snowflake the same question?

A link to the original question

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

Two Inputs and Outputs

1 input

Line 1 of the input contains an integer representing the number of snowflakes.The next n lines, each describing a snowflake.Each snowflake contains 6 integers representing the petal length of the snowflake.The lengths of the petals will all be given in order around the snowflakes (clockwise or counterclockwise), but they can start with any of the 6 petals.For example, the same snowflake can be described as 1 2 3 4 5 6 or 4 3 2 1 6 5

2 output

If all snowflakes are different, output "No two snowflakes are alike", otherwise output "Twin snowflakes found."

Three input and output samples

1 Input example

2

1 2 3 4 5 6

4 3 2 1 6 5

2 Sample output

Twin snowflakes found.

Four Analysis

This problem can be solved by hash table and vector, or by hash table and chained forward star.

Five algorithm design

1 Sum the six petal lengths of the snowflake, then mod a larger prime number P, such as 100003 or 100007

2 Query whether there is the same hash table key in the chain with the same key, if so, query whether there is the same, if so, return 1, otherwise add the key to the Hash table.

3 When the comparison is the same, judge from the clockwise direction and the counterclockwise direction

4 The chain address method is used when dealing with collisions with a hash table.Either vector or chained forward stars can be used, but vector is slower.

Six codes

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();}}// add index i to the linked list with value valstatic 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++) // clockwiseif (snow[a][j] != snow[b][(j + i) % 6])break;if (j == 6) return 1;for (j = 1; j < 6; j++)//counterclockwiseif (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; // If there are multiple sets of test cases, continue to read in}}if (flag == 1)System.out.println("Twin snowflakes found.");elseSystem.out.println("No two snowflakes are alike.");return;}}class node {int to;int next;}

Seven test results