1 条题解
-
2
#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
- 上传者