求助
查看原帖
求助
569085
xjking楼主2023/12/24 11:21
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=998244353;
long long x,y,c;
int h,w,a[N][N],f[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char t;
set<int>s;
long long ksm(long long a,long long b){
    long long s=1;
    while(b){
        if(b&1)s=s*a%M;
        a=a*a%M;
        b/=2;
    }
    return s;
}
void dfs(int x,int y){
	f[x][y]=c;
	for(int i=0; i<4; i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(!f[nx][ny]&&a[nx][ny])dfs(nx,ny);
	}
}
int main(){
	scanf("%d%d", &h, &w);
	for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
			cin>>t;
			if(t=='#')a[i][j]=1;
		}
	}
	for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
			if(!f[i][j]&&a[i][j]){
				c++;
				dfs(i,j);
			}
		}
	}
	for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
			if(!a[i][j]){
				y++;
				if(f[i+1][j]>0)s.insert(f[i+1][j]);
				if(f[i-1][j]>0)s.insert(f[i-1][j]);
				if(f[i][j+1]>0)s.insert(f[i][j+1]);
				if(f[i][j-1]>0)s.insert(f[i][j-1]);
				int w=c-(s.size()-1);
				x+=1ll*w;
				s.clear();
			}
		}
	}
	cout<<x*ksm(y,M-2)%M;
	return 0;
}
2023/12/24 11:21
加载中...