Code Jam Korea 2012 본선 (B)

문제 B. 장터판

생각보다 훨씬 어렵다. 확률 계산을 잘 해야 함. 시간 복잡도는 O(NMK). Large 푸는데 약 2-3초 걸린다.

#include <stdio.h>
#include <string.h>
#include <float.h>
#include <assert.h>
#define OFFSET 4
#define MAX 100

/* -1: ?
 * 0: not a dice (buffer)
 * 1-K: face of the dice
 */
int board[MAX + 2*OFFSET][MAX + 2*OFFSET];
int KK[10];

int mycnt(int n,
	  int x1, int x2=0, int x3=0, int x4=0, int x5=0, int x6=0, int x7=0)
{
	int cnt = 0;
	switch (n) {
	case 7:
		cnt += (x7 == -1) ? 1 : 0;
	case 6:
		cnt += (x6 == -1) ? 1 : 0;
	case 5:
		cnt += (x5 == -1) ? 1 : 0;
	case 4:
		cnt += (x4 == -1) ? 1 : 0;
	case 3:
		cnt += (x3 == -1) ? 1 : 0;
	case 2:
		cnt += (x2 == -1) ? 1 : 0;
	case 1:
		cnt += (x1 == -1) ? 1 : 0;
	}
	return cnt;
}

int pp(int K, int n,
	  int x1, int x2, int x3=0, int x4=0, int x5=0, int x6=0, int x7=0)
{
	int x = -1;
	int t = 1;
	//int cnt = mycnt(n, x1, x2, x3, x4, x5, x6, x7);
	switch (n) {
	case 7:
		x = (x != -1) ? (x) : (x7);
	case 6:
		x = (x != -1) ? (x) : (x6);
	case 5:
		x = (x != -1) ? (x) : (x5);
	case 4:
		x = (x != -1) ? (x) : (x4);
	case 3:
		x = (x != -1) ? (x) : (x3);
	case 2:
		x = (x != -1) ? (x) : (x2);
		x = (x != -1) ? (x) : (x1);
	}
	switch (n) {
	case 7:
		t = t && (x7 == -1 || x7 == x);
	case 6:
		t = t && (x6 == -1 || x6 == x);
	case 5:
		t = t && (x5 == -1 || x5 == x);
	case 4:
		t = t && (x4 == -1 || x4 == x);
	case 3:
		t = t && (x3 == -1 || x3 == x);
	case 2:
		t = t && (x2 == -1 || x2 == x);
		t = t && (x1 == -1 || x1 == x);
	}
	if (t && x != 0) {
		return 1;
	}
	return 0;
}

double pp4(int K, int x1, int x2, int x3, int x4, int x5, int x6, int x7)
{
	int tmp4 = 0;
	tmp4 += pp(K, 4, x1, x2, x3, x4) ? KK[mycnt(3, x5, x6, x7)] : 0;
	tmp4 += pp(K, 4, x2, x3, x4, x5) ? KK[mycnt(3, x1, x6, x7)] : 0;
	tmp4 += pp(K, 4, x3, x4, x5, x6) ? KK[mycnt(3, x1, x2, x7)] : 0;
	tmp4 += pp(K, 4, x4, x5, x6, x7) ? KK[mycnt(3, x1, x2, x3)] : 0;
	tmp4 -= pp(K, 5, x1, x2, x3, x4, x5) ? KK[mycnt(2, x6, x7)] : 0;
	tmp4 -= pp(K, 5, x2, x3, x4, x5, x6) ? KK[mycnt(2, x1, x7)] : 0;
	tmp4 -= pp(K, 5, x3, x4, x5, x6, x7) ? KK[mycnt(2, x1, x2)] : 0;
	return (double) tmp4 / KK[mycnt(7, x1, x2, x3, x4, x5, x6, x7)];
}

double pp3(int K, int x1, int x2, int x3, int x4, int x5)
{
	int tmp3 = 0;
	tmp3 += pp(K, 3, x1, x2, x3) ? KK[mycnt(2, x4, x5)] : 0;
	tmp3 += pp(K, 3, x2, x3, x4) ? KK[mycnt(2, x1, x5)] : 0;
	tmp3 += pp(K, 3, x3, x4, x5) ? KK[mycnt(2, x1, x2)] : 0;
	tmp3 -= pp(K, 4, x1, x2, x3, x4) ? KK[mycnt(1, x5)] : 0;
	tmp3 -= pp(K, 4, x2, x3, x4, x5) ? KK[mycnt(1, x1)] : 0;
	return (double) tmp3 / KK[mycnt(5, x1, x2, x3, x4, x5)];
}

double pp2(int K, int x1, int x2, int x3)
{
	int tmp2 = 0;
	tmp2 += pp(K, 2, x1, x2) ? KK[mycnt(1, x3)] : 0;
	tmp2 += pp(K, 2, x2, x3) ? KK[mycnt(1, x1)] : 0;
	tmp2 -= pp(K, 3, x1, x2, x3);
	return (double) tmp2 / KK[mycnt(3, x1, x2, x3)];
}

double po(int i0, int j0, int S4, int S3, int S2, int K) // wrong
{
	double point = 0.0;
	int kl = 1;
	int kh = K;
	int div = K;
	int gg = 1;
	if (board[i0][j0] != -1) {
		kl = kh = board[i0][j0];
		div = 1;
		gg = 0;
	}
	for (int k = kl; k <= kh; ++k) {
		board[i0][j0] = k;
		double p4, p3, p2;
		double tmp4, tmp3, tmp2;
		p4 = p3 = p2 = 1.0;
		int i, j;
		i = i0;
		j = j0;
		// row
		tmp4 = pp4(K, board[i][j-3], board[i][j-2], board[i][j-1], board[i][j], board[i][j+1], board[i][j+2], board[i][j+3]);
		p4 *= 1.0 - tmp4;
		tmp3 = pp3(K, board[i][j-2], board[i][j-1], board[i][j], board[i][j+1], board[i][j+2]);
		p3 *= 1.0 - tmp3;
		tmp2 = pp2(K, board[i][j-1], board[i][j], board[i][j+1]);
		p2 *= 1.0 - tmp2;
		// column
		tmp4 = pp4(K, board[i-3][j], board[i-2][j], board[i-1][j], board[i][j], board[i+1][j], board[i+2][j], board[i+3][j]);
		p4 *= 1.0 - tmp4;
		tmp3 = pp3(K, board[i-2][j], board[i-1][j], board[i][j], board[i+1][j], board[i+2][j]);
		p3 *= 1.0 -tmp3;
		tmp2 = pp2(K, board[i-1][j], board[i][j], board[i+1][j]);
		p2 *= 1.0 - tmp2;
		// diagonal 1
		tmp4 = pp4(K, board[i-3][j-3], board[i-2][j-2], board[i-1][j-1], board[i][j], board[i+1][j+1], board[i+2][j+2], board[i+3][j+3]);
		p4 *= 1.0 - tmp4;
		tmp3 = pp3(K, board[i-2][j-2], board[i-1][j-1], board[i][j], board[i+1][j+1], board[i+2][j+2]);
		p3 *= 1.0 -tmp3;
		tmp2 = pp2(K, board[i-1][j-1], board[i][j], board[i+1][j+1]);
		p2 *= 1.0 - tmp2;
		// diagonal 2
		tmp4 = pp4(K, board[i-3][j+3], board[i-2][j+2], board[i-1][j+1], board[i][j], board[i+1][j-1], board[i+2][j-2], board[i+3][j-3]);
		p4 *= 1.0 - tmp4;
		tmp3 = pp3(K, board[i-2][j+2], board[i-1][j+1], board[i][j], board[i+1][j-1], board[i+2][j-2]);
		p3 *= 1.0 - tmp3;
		tmp2 = pp2(K, board[i-1][j+1], board[i][j], board[i+1][j-1]);
		p2 *= 1.0 - tmp2;
		//
		p4 = 1.0 - p4;
		p3 = 1.0 - p3;
		p2 = 1.0 - p2;
		p3 -= p4;
		p2 -= (p3 + p4);
		assert(p4 + DBL_EPSILON >= 0);
		assert(p3 + DBL_EPSILON >= 0);
		assert(p2 + DBL_EPSILON >= 0);
		point += (p4 * S4 + p3 * S3 + p2 * S2) / div;
		//printf("! %d, %d: %f, %f, %f\n", i0, j0, p4, p3, p2);
	}
	if (gg) {
		board[i0][j0] = -1;
	}
	//printf("!--------------------\n");
	return point;
}

int main(void)
{
	int T_;
	scanf("%d", &T_);
	for (int i_ = 1; i_ <= T_; ++i_) {
		memset(board, 0, sizeof(board));
		int N, M, K, S4, S3, S2;
		scanf("%d %d %d %d %d %d", &N, &M, &K, &S4, &S3, &S2);
		scanf("%*c");
		for (int i = OFFSET; i < N + OFFSET; ++i) {
			for (int j = OFFSET; j < M + OFFSET; ++j) {
				char c;
				scanf("%c", &c);
				board[i][j] = (c == '?') ? (-1) : (c - '0');
			}
			scanf("%*c");
		}
		KK[0] = 1;
		for (int i = 1; i < 10; ++i)
			KK[i] = KK[i-1] * K;
		double ans = 0.0;
		for (int i = OFFSET; i < N + OFFSET; ++i) {
			for (int j = OFFSET; j < M + OFFSET; ++j) {
				ans += po(i, j, S4, S3, S2, K);
			}
		}
		printf("Case #%d: %.7f\n", i_, ans);
	}
	return 0;
}