原来是图论题吗。

考虑对一个 * 选骨牌意味着什么。它等价于上下选一格左右选一格。

然后考虑建图。二选一的建边。如果一个 * 某一方的 . 是固定的可以建自环。

对每一个连通块，其实就是对每条边选一个点，分类讨论：

• 如果有自环，方案数为 $1$。

• 否则如果是基环树，方案数为 $2$。

• 如果是树，方案数为节点数。

• 否则不合法，方案数为 $0$。

乘法原理即可。可以用并查集维护。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n, m, f[100005], cnt[100005], siz[100005];
bool sc[100005];
const int mod = 998244353;
string s[1005];
const int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};
int tid(int x, int y){
    return (x - 1) * m + y;
}
int find(int x){
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}
void merge(int u, int v){
//    cerr << u << " " << v << "\n";
    int fu = find(u), fv = find(v);
    if (fu == fv){
        if (u == v)
            sc[fu] = 1;
        ++cnt[fu];
        return;
    }
    f[fv] = fu;
    cnt[fu] += cnt[fv] + 1;
    siz[fu] += siz[fv];
    sc[fu] |= sc[fv];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m;
        s[0] = s[n + 1] = "";
        for (int i = 1; i <= m + 2; i++){
            s[0] += "*";
            s[n + 1] += "*";
        }
        for (int i = 1; i <= n; i++){
            cin >> s[i];
            s[i] = "*" + s[i] + "*";
        }
        for (int i = 1; i <= n * m; i++)
            f[i] = i, siz[i] = 1, cnt[i] = 0, sc[i] = 0;
        int ans = 1;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (s[i][j] != '*')
                    continue;
                if (s[i + dx[1]][j + dy[1]] == '.' && s[i + dx[2]][j + dy[2]] == '.')
                    merge(tid(i + dx[1], j + dy[1]), tid(i + dx[2], j + dy[2]));
                else if (s[i + dx[1]][j + dy[1]] == '.')
                    merge(tid(i + dx[1], j + dy[1]), tid(i + dx[1], j + dy[1]));
                else if (s[i + dx[2]][j + dy[2]] == '.')
                    merge(tid(i + dx[2], j + dy[2]), tid(i + dx[2], j + dy[2]));
                else
                    ans = 0;
                if (s[i + dx[3]][j + dy[3]] == '.' && s[i + dx[4]][j + dy[4]] == '.')
                    merge(tid(i + dx[3], j + dy[3]), tid(i + dx[4], j + dy[4]));
                else if (s[i + dx[3]][j + dy[3]] == '.')
                    merge(tid(i + dx[3], j + dy[3]), tid(i + dx[3], j + dy[3]));
                else if (s[i + dx[4]][j + dy[4]] == '.')
                    merge(tid(i + dx[4], j + dy[4]), tid(i + dx[4], j + dy[4]));
                else
                    ans = 0;
            }
        }
        for (int i = 1; i <= n * m; i++){
            if (find(i) == i){
                if (cnt[i] >= siz[i] + 1)
                    ans = 0;
                else if (sc[i] && cnt[i] == siz[i])
                    ans = ans;
                else if (cnt[i] == siz[i])
                    ans = (ans + ans) % mod;
                else
                    ans = (1ll * ans * siz[i]) % mod;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}