Тема: Задачка с www.acmp.ru (# )
Условие: Задача 239. Узор
Извиняюсь за то, что не написал условие, слишком большое...
Вот мое решение, выдает ошибку на 5-ом тесте:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int n1 = 1;
int a1[n1][2] = {{0, 0}};
const int n2 = 2;
int a2[n2][2] = {{0, 0}, {0, 1}};
const int n3 = 3;
int a3[n3][2] = {{0, 0}, {0, 1}, {0, 2}};
const int n4 = 3;
int a4[n4][2] = {{0, 0}, {0, 1}, {1, 1}};
const int ns[] = {-1, n1, n2, n3, n4};
const int inf = 1000000000;
int n, m, k;
int color[10][10];
int cost[10], form[10], paint[10][4];
int memo[10][10][1<<15];
void get(int k, int& n, int (*(&a))[2]) {
if (k == 1) {
n = n1;
a = a1;
} else if (k == 2) {
n = n2;
a = a2;
} else if (k == 3) {
n = n3;
a = a3;
} else {
n = n4;
a = a4;
}
}
void rotate(int k) {
int n;
int (*a)[2];
get(k, n, a);
int mini = 1000, minj = 1000;
for (int i = 0; i < n; ++i) {
int t = a[i][0];
a[i][0] = a[i][1];
a[i][1] = t;
a[i][0] *= -1;
if (a[i][0] < mini || a[i][0] == mini && a[i][1] < minj) {
mini = a[i][0];
minj = a[i][1];
}
}
for (int i = 0; i < n; ++i) {
a[i][0] -= mini;
a[i][1] -= minj;
}
}
bool canPut(int i, int j, int k) {
int n;
int (*a)[2];
get(form[k], n, a);
for (int p = 0; p < n; ++p) {
int i2 = i+a[p][0], j2 = j+a[p][1];
if (!(0 <= i2 && i2 < ::n && 0 <= j2 && j2 < m && color[i2][j2] == paint[k][p]))
return false;
}
return true;
}
void put(int i, int j, int k) {
int n;
int (*a)[2];
get(form[k], n, a);
for (int p = 0; p < n; ++p) {
int i2 = i+a[p][0], j2 = j+a[p][1];
color[i2][j2] = 2;
}
}
void unPut(int i, int j, int k) {
int n;
int (*a)[2];
get(form[k], n, a);
for (int p = 0; p < n; ++p) {
int i2 = i+a[p][0], j2 = j+a[p][1];
color[i2][j2] = paint[k][p];
}
}
int solve(int i, int j) {
if (j == m) {
j = 0;
++i;
}
if (i == n)
return 0;
int state = 0;
for (int k = 0; k < j; ++k) {
if (i+1 < n)
state = state*2+int(color[i+1][k]==2);
if (i+2 < n)
state = state*2+int(color[i+2][k]==2);
}
for (int k = j; k < m; ++k) {
if (i+0 < n)
state = state*2+int(color[i+0][k]==2);
if (i+1 < n)
state = state*2+int(color[i+1][k]==2);
}
if (state < (1<<15) && memo[i][j][state] != -1)
return memo[i][j][state];
int res = inf;
if (color[i][j] == 2) {
res = solve(i, j+1);
} else {
for (int p = 0; p < k; ++p) {
for (int r = 0; r < 4; ++r) {
if (canPut(i, j, p)) {
put(i, j, p);
int cur = cost[p]+solve(i, j+1);
if (cur < res)
res = cur;
unPut(i, j, p);
}
rotate(form[p]);
}
}
}
if (state < (1<<15))
memo[i][j][state] = res;
return res;
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
scanf("%d", &color[i][j]);
for (int i = 0; i < k; ++i) {
scanf("%d%d", &form[i], &cost[i]);
for (int j = 0; j < ns[form[i]]; ++j)
scanf("%d", &paint[i][j]);
}
memset(memo, -1, sizeof(memo));
int res = solve(0, 0);
if (res < inf)
printf("%d\n", res);
else
printf("-1\n");
return 0;
}