Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-05SRM300台を練習していく part7

SRM 315 SillySudoku

|  SRM 315 SillySudoku - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 315 SillySudoku - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6629

意外とやるだけ問題だった。


public class SillySudoku {

	public int[][] perm = {
		{1, 2, 3, 4},
		{1, 2, 4, 3},
		{1, 3, 2, 4},
		{1, 3, 4, 2},
		{1, 4, 2, 3},
		{1, 4, 3, 2},

		{2, 1, 3, 4},
		{2, 1, 4, 3},
		{2, 3, 1, 4},
		{2, 3, 4, 1},
		{2, 4, 1, 3},
		{2, 4, 3, 1},

		{3, 2, 1, 4},
		{3, 2, 4, 1},
		{3, 1, 2, 4},
		{3, 1, 4, 2},
		{3, 4, 2, 1},
		{3, 4, 1, 2},

		{4, 2, 3, 1},
		{4, 2, 1, 3},
		{4, 3, 2, 1},
		{4, 3, 1, 2},
		{4, 1, 2, 3},
		{4, 1, 3, 2},
	};

	public int[][] map;
	public int[][] dmap;
	public int ans = 0;

	public boolean isok() {
		for (int i = 0 ; i < 4 ; i++) {
			int d = 1;
			for (int j = 0 ; j < 4 ; j++) {
				d *= dmap[j][i];
			}
			if (d != 24) {
				return false;
			}
		}

		int[] dx = {0, 2, 0, 2};
		int[] dy = {0, 0, 2, 2};
		for (int d = 0 ; d < 4 ; d++) {
			int dd = dmap[dx[d]][dy[d]] * dmap[dx[d]][1+dy[d]] * dmap[dx[d]+1][dy[d]] * dmap[1+dx[d]][1+dy[d]];
			if (dd != 24) {
				return false;
			}
		}
		return true;
	}

	public void bf(int rec) {
		if (rec == 4) {
			if (isok()) {
				ans++;
			}
			return;
		}
		for (int x = 0 ; x < 24 ; x++) {
			boolean isok = true;
			for (int i = 0 ; i < 4 ; i++) {
				dmap[rec][i] = perm[x][i];
				if (map[rec][i] != 0 && dmap[rec][i] != map[rec][i]) {
					isok = false;
					break;
				}
			}
			if (isok) {
				bf(rec + 1);
			}
		}
	}

	public int countWays(String[] board) {
		map = new int[4][4];
		dmap = new int[4][4];
		for (int i = 0 ; i < 4 ; i++) {
			for (int j = 0 ; j < 4 ; j++) {
				if (board[i].charAt(j) != '-') {
					map[i][j] = board[i].charAt(j) - '0';
				}
			}
		}

		bf(0);
		return ans;
	}
}