不会C不会E,输麻了。
#include<bits/stdc++.h>
#define int long long
#define ctz __builtin_ctz
using namespace std;
const int maxn=1e3+7;
const int mod=998244353;
char mp[maxn][maxn];
int fa[maxn*maxn+7];
int hs(int x,int y){
return x*maxn+y;
}
int findfa(int h){
return fa[h]==h?h:fa[h]=findfa(fa[h]);
}
void mg(int h1,int h2){
int f1=findfa(h1),f2=findfa(h2);
fa[f1]=f2;
}
int h,w;
int cntr;
int cntcc;
int p;
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline int inv(int x){return qpow(x,mod-2);}
signed main(){
cin>>h>>w;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
fa[hs(i,j)]=hs(i,j);
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
char t;
cin>>t;
mp[i][j]=t;
if(t=='.')cntr++;
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(mp[i][j]=='.')continue;
for(int k=1;k<=4;k++){
int di=i+dx[k];
int dj=j+dy[k];
if(mp[di][dj]=='#')mg(hs(di,dj),hs(i,j));
}
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(mp[i][j]=='.')continue;
if(findfa(hs(i,j))==hs(i,j))cntcc++;
}
}
// cout<<cntcc<<endl;
vector<int> nw;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
while(!nw.empty())nw.pop_back();
if(mp[i][j]=='#')continue;
int ansij=cntcc+1;
for(int k=1;k<=4;k++){
int di=i+dx[k];
int dj=j+dy[k];
if(mp[di][dj]!='#')continue;
int h=findfa(hs(di,dj));
bool f=false;
for(int l=0;l<nw.size();l++){
if(nw[l]==h){
f=true;
break;
}
}
if(!f){
nw.push_back(h);
ansij--;
}
}
// cout<<ansij<<" "<<i<<" "<<j<<endl;
p+=ansij;
}
}
// cout<<p<<" "<<cntr<<endl;
cout<<p*inv(cntr)%mod;
}