문제 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;
}
