题解
要求最大值，所以考虑(min-max)
[max(S)=sum_{T|S}min(T)^{|T|+1}
]
那么一个集合的(min)如何求呢，我们一共有(n*(m-1)+m*(n-1))个相邻的对，令该集合涉及到的相邻的对的个数为(x),那么期望的时间为(frac{n*(m-1)+m*(n-1)}{x})。
所以我们可以在轮廓线上(dp)，设(dp[i][j][s][num])表示做到了((i,j)),当前状态为(s),有(num)个相邻对。
我们(dp)的内容是系数和，最后根据不同的(num)再乘上个系数就行了。
因为拐角的状态不用记，所以好写一些。
代码
#include<bits/stdc++.h>
#define N 7
#define M 103
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,m;
char a[N][M];
ll dp[2][1<<6][N*M*2],ans;
inline ll power(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
inline void MOD(ll &x){x=x>=mod?x-mod:x;}
inline ll ni(ll x){return power(x,mod-2);}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",a[i]+1);
}
int sum=n*m*2-n-m;
int now=1,pre=0;
dp[now][0][0]=mod-1;
int maxn=(1<<n)-1;
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j){
swap(now,pre);
memset(dp[now],0,sizeof(dp[now]));
for(int s=0;s<=maxn;++s)
for(int k=0;k<=sum;++k)if(dp[pre][s][k]){
int S=s&(maxn^(1<<(j-1)));
MOD(dp[now][S][k]+=dp[pre][s][k]);
if(a[j][i]=='*'){
S|=(1<<j-1);
int delta=(i!=1&&(s&(1<<j-1))==0)+(j!=1&&(s&(1<<j-2))==0)+(i<m)+(j<n);
MOD(dp[now][S][k+delta]+=mod-dp[pre][s][k]);
}
}
}
for(int i=1;i<=sum;++i){
ll inv=power(i,mod-2);
for(int s=0;s<=maxn;++s)MOD(ans+=dp[now][s][i]*inv%mod);
}
ans=ans*sum%mod;
cout<<ans;
return 0;
}