cube_momodi.java

第四届百度杯预赛解题报告 武汉大学20090315

import java.util.Scanner;

public class Main {
	static Scanner cin = new Scanner(System.in);
	static int[][] z;

	static void gen() {
		z = new int[12][24];
		for (int i = 0; i < 6; ++i) {
			for (int j = 0; j < 24; ++j) {
				z[i][j] = j;
			}
		}
		{
			int[] t = z[0];
			t[0] = 1;
			t[1] = 3;
			t[3] = 2;
			t[2] = 0;
			t[4] = 10;
			t[5] = 11;
			t[6] = 4;
			t[7] = 5;
			t[8] = 6;
			t[9] = 7;
			t[10] = 8;
			t[11] = 9;
		}
		{
			int[] t = z[1];
			t[20] = 22;
			t[22] = 23;
			t[23] = 21;
			t[21] = 20;
			t[12] = 18;
			t[13] = 19;
			t[14] = 12;
			t[15] = 13;
			t[16] = 14;
			t[17] = 15;
			t[18] = 16;
			t[19] = 17;
		}
		{
			int[] t = z[2];
			t[5] = 13;
			t[13] = 12;
			t[12] = 4;
			t[4] = 5;
			t[0] = 6;
			t[2] = 14;
			t[6] = 20;
			t[14] = 22;
			t[20] = 19;
			t[22] = 11;
			t[11] = 2;
			t[19] = 0;
		}
		{
			int[] t = z[3];
			t[8] = 16;
			t[16] = 17;
			t[17] = 9;
			t[9] = 8;
			t[1] = 7;
			t[3] = 15;
			t[7] = 21;
			t[15] = 23;
			t[21] = 18;
			t[23] = 10;
			t[10] = 3;
			t[18] = 1;
		}
		{
			int[] t = z[4];
			t[6] = 14;
			t[14] = 15;
			t[15] = 7;
			t[7] = 6;
			t[2] = 13;
			t[3] = 5;
			t[5] = 20;
			t[13] = 21;
			t[20] = 16;
			t[21] = 8;
			t[16] = 3;
			t[8] = 2;
		}
		{
			int[] t = z[5];
			t[18] = 10;
			t[10] = 11;
			t[11] = 19;
			t[19] = 18;
			t[1] = 4;
			t[0] = 12;
			t[4] = 22;
			t[12] = 23;
			t[22] = 17;
			t[23] = 9;
			t[17] = 1;
			t[9] = 0;
		}
		for (int i = 6; i < 12; ++i) {
			z[i] = turn3(z[i - 6]);
		}
	}

	static int[] turn3(int[] a) {
		int[] ans = new int[24];
		for (int i = 0; i < 24; ++i) {
			int k = i;
			for (int j = 0; j < 3; ++j) {
				k = a[k];
			}
			ans[i] = k;
		}
		return ans;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		gen();
		int ca = cin.nextInt();
		while (ca-- > 0) {
			int[] S = input();
			int[] T = input();
			System.out.println(solve(S, T));
		}
	}

	static int solve(int[] Sa, int[] Ta) {
		long S = zz(Sa), T = zz(Ta);
		int lim = 0;
		while (true) {
			long[] Q = new long[3000000];
			Hash[] H1 = new Hash[M], H2 = new Hash[M];
			bfs(Q, H1, S, lim);
			bfs(Q, H2, T, lim);
			++lim;
			int k = findMin(H1, H2);
			if (k != 100) {
				return k;
			}
		}
	}

	static void bfs(long[] Q, Hash[] H, long S, int lim) {
		Q[0] = S;
		insert(H, S, 0);
		int[] tmp = new int[24];
		int[] des = new int[24];
		for (int s = 0, t = 1; s < t; ++s) {
			long v = Q[s];
			int d = find(H, v);
			if (d >= lim) {
				continue;
			}
			zz(v, tmp);
			for (int i = 0; i < 12; ++i) {
				for (int j = 0; j < 24; ++j) {
					des[z[i][j]] = tmp[j];
				}
				long p = zz(des);
				if (find(H, p) == -1) {
					insert(H, p, d + 1);
					Q[t++] = p;
				}
			}
		}
	}

	static void zz(long k, int[] ans) {
		for (int i = 23; i >= 0; --i) {
			ans[i] = (int) (k % 6);
			k /= 6;
		}
	}

	static int findMin(Hash[] H1, Hash[] H2) {
		int ans = 100;
		for (int i = 0; i < M; ++i) {
			for (Hash pt = H1[i]; pt != null; pt = pt.next) {
				int a = find(H2, pt.k);
				if (a != -1 && a + pt.ans < ans) {
					ans = a + pt.ans;
				}
			}
		}
		return ans;
	}

	static long zz(int[] a) {
		long ans = 0;
		for (int i = 0; i < 24; ++i) {
			ans = ans * 6 + a[i];
		}
		return ans;
	}

	static int[] input() {
		int[] ans = new int[24];
		for (int i = 0; i < 24; ++i) {
			ans[i] = toInt(cin.next().charAt(0));
		}
		return ans;
	}

	static int toInt(char c) {
		if (c == 'W') {
			return 0;
		} else if (c == 'Y') {
			return 1;
		} else if (c == 'R') {
			return 2;
		} else if (c == 'O') {
			return 3;
		} else if (c == 'G') {
			return 4;
		} else if (c == 'B') {
			return 5;
		} else {
			System.out.println("error\n");
			while (true)
				;
		}
	}

	static final int M = 2325881;
	static int cnt = 0;

	static void insert(Hash[] H, long k, int ans) {
		int v = (int) (k % M);
		Hash tmp = new Hash();
		tmp.k = k;
		tmp.ans = ans;
		tmp.next = H[v];
		H[v] = tmp;
	}

	static int find(Hash[] H, long k) {
		for (Hash pt = H[(int) (k % M)]; pt != null; pt = pt.next) {
			if (pt.k == k) {
				return pt.ans;
			}
		}
		return -1;
	}
}

class Hash {
	long k;
	int ans;
	Hash next;
}