GCJ2010 Round2 A "Elegant Diamond"

問題：http://code.google.com/codejam/contest/dashboard?c=635102#s=p0

• サイズkのElegant Diamondのパターンを作成
• 作ったDiamondのパターンが入力データと一致するか判定
• 一致しなければサイズk+1のパターンを作成
• パターンはkが奇数個あるいは偶数個で再帰的に作成

import java.io.File;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class A {
	public static void main(String[] args) throws Exception {
		// new A("src/A-sample");
//		new A("src/A-small-attempt0");
		 new A("src/A-large");
	}

	public A(String filename) throws Exception {
		Scanner scan = new Scanner(new File(filename + ".in"));
		PrintWriter out = new PrintWriter(new File(filename + ".out"));
		solve(scan, out);
	}

	private void solve(Scanner scan, PrintWriter pw) {
		int T = scan.nextInt();
		for (int t = 0; t++ < T;) {
			K = scan.nextInt();
			int[][] in = new int[K][K];
			for (int i = 0; i < K; i++) {
				for (int j = 0; j <= i; j++) {
					in[i - j][j] = scan.nextInt();
				}
			}
			for (int i = K - 1; i > 0; i--) {
				for (int j = 0; j < i; j++) {
					in[K - j - 1][K - i + j] = scan.nextInt();
				}
			}
			int k = K;
			for (; !isElegant(k, in); k++)
				;
			String result = "" + (k * k - K * K);
			pw.printf("Case #%d: %s\n", t, result);
		}
		pw.flush();
	}

	private boolean isElegant(int k, int[][] in) {
		p = 1;
		int[][] pat = createPattern(k);
		for (int i = 0; i <= k - K; i++) {
			jl: for (int j = 0; j <= k - K; j++) {
				Map<Integer, Integer> map = new HashMap<Integer, Integer>();
				for (int r = 0; r < K; r++) {
					for (int c = 0; c < K; c++) {
						if (!map.containsKey(pat[i + r][j + c])) {
							map.put(pat[i + r][j + c], in[r][c]);
						} else if (map.get(pat[i + r][j + c]) != in[r][c]) {
							continue jl;
						}
					}
				}
				return true;
			}
		}
		return false;
	}

	private int[][] createPattern(int k) {
		int[][] a = new int[k][k];
		if (k == 1) {
			a[0][0] = a[k - 1][k - 1] = p++;
			return a;
		} else if (k == 2) {
			a[0][0] = a[1][1] = p++;
			a[0][1] = a[1][0] = p++;
			return a;
		}
		a[0][0] = a[k - 1][k - 1] = p++;
		for (int r = 1; r < k; r++) {
			a[0][r] = a[r][0] = a[k - 1][k - 1 - r] = a[k - 1 - r][k - 1] = p++;
		}
		int[][] b = createPattern(k - 2);
		for (int r = 0; r < b.length; r++) {
			for (int c = 0; c < b[r].length; c++) {
				a[r + 1][c + 1] = b[r][c];
			}
		}
		return a;
	}

	int p = 0;
	int K;
}