1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #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; }
|