AcWing 2926. 小Z的房间
原题链接
困难
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
const int N=10,M=100;
int n,m;
int a[N][N];
int cnt;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ma1[M][M],ma2[M][M];
int ans=1;
int f=1;
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) {
char ch=getchar();
while(ch!='.'&&ch!='*') ch=getchar();
if(ch=='.') a[i][j]=++cnt;
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(!a[i][j]) continue;
for(int l=0;l<4;++l) {
int x=i+dx[l],y=j+dy[l];
if(!x||!y||x>n||y>m) continue;
if(!a[x][y]) continue;
ma1[a[i][j]][a[x][y]]++;
ma2[a[i][j]][a[i][j]]++;
}
}
}
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j) ma2[i][j]=(ma2[i][j]-ma1[i][j]+mod)%mod;
cnt--;
for(int i=1;i<=cnt;++i) {
for(int j=i+1;j<=cnt;++j) {
while(ma2[i][i]) {
int div=ma2[j][i]/ma2[i][i];
for(int l=i;l<=cnt;++l) ma2[j][l]=(ma2[j][l]-1ll*div*ma2[i][l]%mod+mod)%mod;
swap(ma2[i],ma2[j]);
f=-f;
}
swap(ma2[i],ma2[j]);
f=-f;
}
}
ans=f;
for(int i=1;i<=cnt;++i) ans=(1ll*ans*ma2[i][i]%mod+mod)%mod;
printf("%d\n",ans);
return 0;
}