#include <stdio.h>using namespace std;#define LL long long int n, m, i;LL f[10][512]; void dfs(int j, int opt1, int opt2, int u1, int u2){     if (j == m)     {        if (!u1 && !u2) f[i + 1][opt2] += f[i][opt1];         return;     }     // Put this block     if (!u2)     {        if (!u1)        {           dfs(j+1, opt1<<1, (opt2<<1)+1, 0, 0); // Case 1           dfs(j+1, opt1<<1, (opt2<<1)+1, 1, 0); // Case 2           dfs(j+1, opt1<<1, (opt2<<1)+1, 0, 1); // Case 3        }        dfs(j+1, (opt1<<1)+1-u1, (opt2<<1)+1, 0, 1); // Case 4        dfs(j+1, (opt1<<1)+1-u1, (opt2<<1)+1, 1, 1); // Case 5     }     // NO put or Already put this block     if (!u1) dfs(j+1, opt1<<1, (opt2<<1)+u2, 1, 1); // Case 6     dfs(j+1, (opt1<<1)+1-u1, (opt2<<1)+u2, 0, 0); // Case 7} int main(){    scanf("%d %d", &n, &m);    if (n < m) { n ^= m; m ^= n; n ^= m; }    f[0][(1<<m)-1] = 1;    for (i = 0; i < n; ++i)        dfs(0, 0, 0, 0, 0);    printf("%I64d", f[n][(1<<m)-1]);    return 0;}

#include <iostream>#include <cstring>#include <cstdio>#define INF 16843009using namespace std;int g[71], Tmi[] = {1, 2, 4, 8, 16, 32, 64, 128};int f[2][1 << 8][1 << 8];int n, m, x, stI, stJ,ans=INF;//状态压缩，0代表不放，1代表放//对每一行DFS时填它的上一行void dfs (int k, int opt1, int opt2, int cnt) {       //填完k列后，如果前两行中出现了连续0，退出    if (k > 0 && (stI & Tmi[k - 1]) == 0 && (opt1 & Tmi[k - 1]) == 0) return;    if (k > 1 && (opt1 & Tmi[k - 1]) == 0 && (opt1 & Tmi[k - 2]) == 0) return;    if (k == m) {        if (f[x ^ 1][stI][stJ] != INF)            f[x][opt1][opt2] = min (f[x][opt1][opt2], f[x ^ 1][stI][stJ] + cnt);        return;    }    //这一列不填    dfs (k + 1, opt1, opt2, cnt);    //填上一行,和当前一行的同一列    if ( (opt1 & Tmi[k]) == 0 && (opt2 & Tmi[k]) == 0)        dfs (k + 1, opt1 | Tmi[k], opt2 | Tmi[k], cnt + 1);       //填上一行的连续两列    if (k < (m - 1) && (opt1 & Tmi[k]) == 0 && (opt1 & Tmi[k + 1]) == 0)        dfs (k + 1, opt1 | Tmi[k + 1] | Tmi[k], opt2, cnt + 1);}int main() {    scanf ("%d %d", &n, &m);    char st[71];    for (int i = 1; i <= n; i++) {        scanf ("%s", st + 1);        for (int j = 1; j <= m; j++)            g[i] = g[i] << 1 | (st[j] == ‘*‘);    }    memset (f, 1, sizeof f);    f[1][Tmi[m] - 1][g[1]] = 0;    for (int k = 1; k <= n; k++) {        for (int i = 0; i < Tmi[m]; i++)            for (int j = 0; j < Tmi[m]; j++) {                if (f[x ^ 1][i][j] != INF){                                   stI = i, stJ = j;                    dfs (0, j, g[k + 1], 0);                }            }        memset (f[x ^ 1], 1, sizeof f[x ^ 1]);        x ^= 1;    }    x ^= 1;    for (int i = 0; i < Tmi[m]; i++)        for (int j = 0; j < Tmi[m]; j++)            if (f[x][i][j] > 0)     ans = min (ans, f[x][i][j]);    printf ("%d", ans);}