1ms+370mb

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct DATA {
    int cnt, a, b, c;
    DATA(int q) { // 将 int 转换为状态
        cnt = q & 3;
        a = q >> 2 & 31;
        b = q >> 7 & 31;
        c = q >> 12 & 31;
    }
    DATA(int cnt, int a, int b, int c) : cnt(cnt), a(a), b(b), c(c) {}
    operator int() { // 将状态转换为 int
        if (a > b) swap(a, b);
        if (b > c) swap(b, c);
        if (a > b) swap(a, b);
        return cnt | (a << 2) | (b << 7) | (c << 12);
    }
    DATA replace(int a, int b, int d = 0) { // 替换插头的位置，d 代表 cnt 是否加 1
        DATA c = *this;
        if (c.a == a) c.a = b;
        else if (c.b == a) c.b = b;
        else if (c.c == a) c.c = b;
        c.cnt += d;
        return c;
    }
};
int n, m;
const int T = 10007;
struct Hash { // 哈希表
    int fst[T], nxt[T], tot, v[T], k[T];
    void insert(int d, int vv) {
        int h = d % T;
        v[++tot] = vv;
        k[tot] = d;
        nxt[tot] = fst[h];
        fst[h] = tot;
    }
    int find(int d) {
        int h = d % T;
        int p = fst[h];
        while (p && k[p] != d) p = nxt[p];
        return v[p];
    }
    void clear() {
        tot = 0;
        memset(fst, 0, sizeof fst);
    }
}mp[2];
long long f[2][MAXN], cnt;
void S(int d, int a, long long b) { // 更新答案函数
    int q = mp[d].find(a);
    if (q) f[d][q] += b;
    else mp[d].insert(a, ++cnt), f[d][cnt] = b;
}
char ch[44][44];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", ch[i] + 1);
    f[0][1] = 1, mp[0].insert(DATA{0, 0, 0, 0}, 1);
    for (int i = 1, t = 0; i <= n; i++) {
        for (int j = 1; j <= mp[t].tot; j++) { // 新一行状态要向右平移
            DATA ori = mp[t].k[j]; 
            if (ori.a) ori.a++; 
            if (ori.b) ori.b++; 
            if (ori.c) ori.c++;
            mp[t].k[j] = ori;
        }
        for (int j = 1; j <= m; j++) {
            t ^= 1, cnt = 0;
            mp[t].clear();
            for (int k = 1; k <= mp[t ^ 1].tot; k++) {
                DATA s = mp[t ^ 1].k[k];
                long long ans = f[t ^ 1][mp[t ^ 1].v[k]];
                int r = s.a == j || s.b == j || s.c == j, 
                    d = s.a == j + 1 || s.b == j + 1 || s.c == j + 1;
                if (ch[i][j] == '#') { // case 1
                    S(t, s, ans);
                } else if (!r && !d) { // case 2
                    S(t, s, ans);
                    if (ch[i + 1][j] == '.' && s.cnt < 3)
                        S(t, s.replace(0, j, 1), ans);
                } else if (!r && d) { // case 3
                    if (ch[i + 1][j] == '.') S(t, s.replace(j + 1, j), ans);
                    if (ch[i][j + 1] == '.') S(t, s, ans);
                } else if (r && !d) { // case 4
                    if (ch[i][j + 1] == '.') S(t, s.replace(j, j + 1), ans);
                    S(t, s.replace(j, 0), ans);
                } else if (r && d) { // case 5
                    "go to hell";
                }
            }
        }
        if (i == n) {
            printf("%lld\n", f[t][mp[t].find(DATA{3, 0, 0, 0})]);
        }
    }
    return 0;
}