C++14(g++5.4) 解法, 执行用时: 38ms, 内存消耗: 9568K, 提交时间: 2020-08-09 12:48:56
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=505;
ll T,n,m,tot,cnt,fa[maxn*maxn],id[maxn][maxn];
ll End[maxn*maxn],Next[maxn*maxn],Last[maxn*maxn];
ll bl[maxn*maxn],G[maxn][maxn];
char s[maxn][maxn];
bool flag;
void Addedge(ll x,ll y)
{
End[++cnt]=y;
Next[cnt]=Last[x],Last[x]=cnt;
}
void DFS(ll x)
{
fa[x]=tot;
for(ll i=Last[x];i;i=Next[i])
if(fa[End[i]]<0) DFS(End[i]);
}
ll Gauss(ll n)
{
ll temp=1,mark=0;
for(ll i=1;i<=n;i++)
{
for(ll j=i+1;j<=n;j++)
while(G[j][i])
{
ll t=G[i][i]/G[j][i];
for(ll k=i;k<=n;k++) G[i][k]=(G[i][k]-t*G[j][k]%mod+mod)%mod;
swap(G[i],G[j]),mark^=1;
}
temp=temp*G[i][i]%mod;
}
if(mark) temp=mod-temp;
return (temp%mod+mod)%mod;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&m),tot=cnt=flag=0;
memset(Last,0,sizeof(Last));
memset(fa,-1,sizeof(fa));
memset(id,0,sizeof(id));
for(ll i=1;i<=n;i++) scanf("%s",s[i]+1);
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++) id[i][j]=(i-1)*m+j;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(s[i][j]!='.')
{
ll tx=i,ty=j;
if(s[i][j]=='U') tx--;
else if(s[i][j]=='D') tx++;
else if(s[i][j]=='L') ty--;
else ty++;
Addedge(id[tx][ty],id[i][j]);
}
DFS(0);
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(s[i][j]=='.') tot++,DFS(id[i][j]);
for(ll i=1;i<=n&&!flag;i++)
for(ll j=1;j<=m&&!flag;j++)
if(fa[id[i][j]]<0) flag=true;
if(flag){puts("0");continue;}
if(!tot){puts("1");continue;}
memset(G,0,sizeof(G));
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(s[i][j]=='.')
{
ll f=fa[id[i][j]];
if(fa[id[i-1][j]]!=f) G[f][f]++,G[f][fa[id[i-1][j]]]--;
if(fa[id[i][j-1]]!=f) G[f][f]++,G[f][fa[id[i][j-1]]]--;
if(fa[id[i+1][j]]!=f) G[f][f]++,G[f][fa[id[i+1][j]]]--;
if(fa[id[i][j+1]]!=f) G[f][f]++,G[f][fa[id[i][j+1]]]--;
}
printf("%lld\n",Gauss(tot));
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 533ms, 内存消耗: 1268K, 提交时间: 2022-08-18 14:00:37
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
#define P 1000000007
#define ll long long
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int Pow(int x,int y)
{
int s=1;
for(;y;y>>=1,x=(ll)x*x%P)if(y&1)s=(ll)s*x%P;
return s;
}
int t,n,m,N,i,j,k,l,ans,v[205][205],f[205][205],a[305][305];
char c[205][205];
int dfs(int x,int y)
{
if(v[x][y]==2)return f[x][y];
if(v[x][y]==1)return -1;
v[x][y]=1;
if(c[x][y]=='.')f[x][y]=++N;
else if(c[x][y]=='L')f[x][y]=dfs(x,y-1);
else if(c[x][y]=='R')f[x][y]=dfs(x,y+1);
else if(c[x][y]=='U')f[x][y]=dfs(x-1,y);
else f[x][y]=dfs(x+1,y);
v[x][y]=2;
return f[x][y];
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
N=0;
for(i=1;i<=n;i++)scanf("%s",c[i]+1);
memset(v,0,sizeof(v));
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
for(i=1;i<=n;i++)v[i][0]=v[i][m+1]=2;
for(i=1;i<=m;i++)v[0][i]=v[n+1][i]=2;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(!v[i][j])if(!~dfs(i,j))goto xxx;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(c[i][j]=='.')for(k=0;k<4;k++)
{
a[f[i+dx[k]][j+dy[k]]][f[i][j]]--;
a[f[i][j]][f[i][j]]++;
}
for(i=1;i<=N;i++)for(j=1;j<=N;j++)if(a[i][j]<0)a[i][j]+=P;
for(i=ans=1;i<N;i++)
{
for(j=i;j<=N;j++)if(a[j][i])break;
if(j>N)break;
if(j!=i)for(ans=P-ans,k=i;k<=N;k++)swap(a[j][k],a[i][k]);
for(j=i+1,l=Pow(a[i][i],P-2);j<=N;j++)for(k=N;k>=i;k--)a[j][k]=(a[j][k]-(ll)a[i][k]*a[j][i]%P*l%P+P)%P;
}
for(i=1;i<=N;i++)ans=(ll)ans*a[i][i]%P;
cout<<ans<<endl;
continue;
xxx:puts("0");
}
return 0;
}
