Настройки поиска

#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;
}