SGU 132 Another Chocolate Maniac by iloahz@Attiix

sgu132.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 72;
const int MAXS = 1 << 7;

int m, n, s;
int a[MAXN];
int f[2][MAXS][MAXS];
int l, r;

void init(){
    scanf("%d%d", &m, &n);
    char s[10];
    for (int i = 0;i < m;i++){
        a[i] = 0;
        scanf("%s", s);
        for (int j = 0;j < n;j++){
            a[i] <<= 1;
            a[i] |= s[j] == '*';
        }
    }
}

void dfs(int a, int b, int c, int i, int j, int d){
    if (i >= s){
        f[r][b ^ s][c] = min(f[r][b ^ s][c], d);
        return;
    }
    if ((b & i)) dfs(a, b, c, i << 1, 0, d);
    else{
        if ((a & i) && j < 1) dfs(a, b, c, i << 1, j + 1, d);
        if ((c & i) == 0) dfs(a, b | i, c | i, i << 1, 0, d + 1);
        if ((b & (i << 1)) == 0) dfs(a, b | i | (i << 1), c, i << 2, 0, d + 1);
    }
}

int dp(){
    s = 1 << n;
    l = 0;
    r = 1;
    memset(f, 1, sizeof(f));
    f[l][s - 1][s - 1] = 0;
    a[m] = a[m + 1] = s - 1;
    for (int i = 0;i <= m + 1;i++){
        for (int j = 0;j < s;j++)
            for (int k = 0;k < s;k++)
                f[r][j][k] = 1 << 30;
        for (int j = 0;j < s;j++){
            for (int k = 0;k < s;k++){
                if (f[l][j][k] < n * m) dfs(j | s, k | s, a[i], 1, 0, f[l][j][k]);
            }
        }
        l ^= 1;
        r ^= 1;
    }
    printf("%d\n", f[l][s - 1][s - 1]);
}

int main(){
#ifdef  ATTIIX
    freopen("sgu132.in", "r", stdin);
#endif
    init();
    dp();
}