# Another Chocolate Maniac

## 题目描述

Bob really LOVES chocolate. He thinks he never gets enough. Imagine his joy when his parents told him that they would buy him many rectangular chocolate pieces for his birthday. A piece of chocolate is a $2 \times 1$ or $1 \times 2$ rectangle. Bob’s parents also bought him a nice birthday cake, which can be imagined as a matrix having $M$ rows and $N$ columns. Some positions on the cake are occupied by candles, the others are empty. Bob’s parents asked their son to place as many chocolate pieces as he can on the empty squares on the cake, in such a manner that no two chocolate pieces overlap. However, he would like to keep the chocolate pieces to himself. That’s why, he wants to place only a minimal amount of them on the cake and keep the rest. In order not to make Mon and Dad suspicious, Bob wants to place the chocolate pieces in such a way, that no other piece may be placed on the cake (that is, there won’t exist any two adjacent empty squares). Find the minimal number of pieces which need to be placed on the cake, so that they do not overlap and no extra piece may be added.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 80;
static const int M = 8;
int n, m, f[2][1 << M][1 << M], mp[N];
void input() {
io > n > m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
char c; io > c, (mp[i] <<= 1) += c == '*';
}
mp[0] = mp[n + 1] = mp[n + 2] = (1 << m) - 1;
}
void init() { memset(f, 0x1f, sizeof f), f[0][mp[0]][mp[1]] = 0; }
bool check(int s) {
bool flag = false;
for (int i = 0; i < m; s >>= 1, ++ i) {
if (s & 1) flag = false;
else { if (flag) return false; flag = true; }
}
return true;
}
void update(int x, int a, int b, int s, int val, int p) {
if (check(b) && ! ((1 << m) - 1 - a & (1 << m) - 1 - b)) minify(f[x][b][s], val);
for (int i = p; i < m; ++ i)
if (! (b & 1 << i)) {
if (! (s & 1 << i)) update(x, a, b | 1 << i, s | 1 << i, val + 1, i + 1);
if (i && ! (b & 1 << i - 1)) update(x, a, b | 1 << i | 1 << i - 1, s, val + 1, i + 1);
}
}
void process() {
int cur = 0;
for (int i = 1; i <= n + 1; cur ^= 1, ++ i) {
memset(f[cur ^ 1], 0x1f, sizeof f[cur ^ 1]);
for (int j = 0; j < 1 << m; ++ j)
for (int k = 0; k < 1 << m; ++ k)
if (f[cur][j][k] < 5e8) update(cur ^ 1, j, k, mp[i + 1], f[cur][j][k], 0);
}
io < f[cur][(1 << m) - 1][(1 << m) - 1] < '\n';
}

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot