SGU 132 Another Chocolate Maniac

題目敘述：

給你一塊M*N的蛋糕，有些地方有蠟燭

你要把沒有蠟燭的地方用1*2的巧克力塊覆蓋

而且如果有可以覆蓋的地方就一定要覆蓋

請用最少的巧克力，問最少要幾塊

M <= 70
N <= 7

一看到N好小，而且又發現因為是1*2的

所以當你要放在某一層時，最多影響到那前一層

所以無後效性，符合DP的原則，且是狀態壓縮DP

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

接下來比較麻煩的部份就是要怎麼去DP他

為了讓code便簡潔，我使用的方式是這樣：

對於某一層去放，放置的方式只有兩種－此格和下方格，此格和右方格

可以確定這樣便可以實現所有的可能

接著有些東西需要判斷，就是一定要放滿的這個規則

總之就寫成一個DFS

而因為那個規則，dp必須要包含上層及此層兩項

O(M*(2^(2N)*N) 約10^7

//By momo
#include<cstdio>
#include<algorithm>
#define N 100
#define INF 999999999
using namespace std;

int n, m, pos, tbl[N];
int dp[2][1<<7][1<<7];
int T(int x){ return 1<<x; }

void init();
void dfs();
void solve();
void output();

int main()
{
    init();
    solve();
    output();
}

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

    tbl[0] = T(m)-1;
    for(int i = 0; i < T(m); i++)
        for(int j = 0; j < T(m); j++)
            dp[0][i][j] = dp[1][i][j] = INF;
}

void dfs(int x, int pv, int nw, int nx, int cnt)
{
    if(x == m)
    {
        dp[1-pos][nw][nx] = min(cnt, dp[1-pos][nw][nx]);
        return;
    }
    bool a = (pv & T(x));
    bool b = (nw & T(x));
    bool c = (nx & T(x));
    if(b) dfs(x+1, pv, nw, nx, cnt);
    else
    {
        if((x == 0 || (nw & T(x-1))) && a)
            dfs(x+1, pv, nw, nx, cnt);
        if(x != m-1 && (nw & T(x+1)) == 0)
            dfs(x+1, pv, nw+T(x)+T(x+1), nx, cnt+1);
        if(!c) dfs(x+1, pv, nw+T(x), nx+T(x), cnt+1);
    }
}

void solve()
{
    dp[pos = 0][T(m)-1][tbl[1]] = 0;
    for(int i = 0; i < n; i++, pos = 1-pos)
    {
        for(int j = 0; j < T(m); j++)
            for(int k = 0; k < T(m); k++)
                dp[1-pos][j][k] = INF;
       
        for(int j = 0; j < T(m); j++)
        {
            if((tbl[i]&j) != tbl[i]) continue;
            for(int k = 0; k < T(m); k++)
            {
                if(dp[pos][j][k] == INF) continue;
                dfs(0, j, k, tbl[i+2], dp[pos][j][k]);
            }
        }
    }
}

void output()
{
    int ans = INF;
    for(int i = 0; i < T(m); i++)
        if((tbl[n]&i) == tbl[n])
            ans = min(ans, dp[pos][i][0]);
    printf("%d\n", ans);
}