1 条题解

  • 2
    @ 2026-2-2 10:45:55
    #include<bits/stdc++.h>
    using namespace std;
    #define nx x+dx[i]
    #define ny y+dy[i]
    #define int long long
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
    const int N=1010,P=998244353;
    int v[N][N],a[N][N];int n,m,cnt;
    int qpow(int a,int b){int res=1;for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;return res;}
    void bfs(int xx,int yy)
    {
    	deque<pair<int,int>>q;q.push_back({xx,yy});
    	a[xx][yy]=cnt;
    	while(!q.empty())
    	{
    		int x=q.front().first,y=q.front().second;q.pop_front();
    		for(int i=0;i<4;i++)if(nx>0&&nx<=n&&ny>0&&ny<=m&&v[nx][ny]&&!a[nx][ny])
    			q.push_back({nx,ny}),a[nx][ny]=cnt;
    	}
    }
    signed main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    	{
    		string st;cin>>st;
    		for(int j=0;j<m;j++)v[i][j+1]=st[j]=='#';
    	}
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    		if(v[i][j]&&!a[i][j])
    			cnt++,bfs(i,j);
    	int sum=0,ans=0;
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!v[i][j])
    	{
    		int x=i,y=j;
    		set<int>s;
    		for(int i=0;i<4;i++)if(nx>0&&nx<=n&&ny>0&&ny<=m&&v[nx][ny])
    			s.insert(a[nx][ny]);
    		int ss=s.size();
    		ans+=cnt;
    		if(ss==0)ans++;
    		if(ss==2)ans--;
    		if(ss==3)ans-=2;
    		if(ss==4)ans-=3;
    		sum++;
    	}
    	int d=__gcd(sum,ans);sum/=d,ans/=d;ans%=P;
    	int anss=ans*qpow(sum,P-2)%P;
    	cout<<anss;
    	return 0;
    }
    • 1

    信息

    ID
    8273
    时间
    2000ms
    内存
    1024MiB
    难度
    7
    标签
    递交数
    16
    已通过
    9
    上传者