1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=304,MOD=1e9+7; const int DIR[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
#define cs const int & inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;} inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;} inline int Mul(cs a,cs b){return 1ll*a*b%MOD;} inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a);b>>=1;}return r;}
struct DSU{ int fa[N*N]; int Find(int u){return fa[u]==u?u:fa[u]=Find(fa[u]);} bool Merge(int u,int v){ u=Find(u),v=Find(v); if(u==v) return false; fa[u]=v; return true; } void Init(int siz){for(int i=0;i<=siz;i++) fa[i]=i;} }Ds;
int n,m; int mat[N][N],imap[N*N]; char maz[N][N];
inline int Idx(int x,int y){return (x<1 || x>n || y<1 || y>m)?0:(x-1)*m+y;} void Link(int ux,int uy,int vx,int vy){ int u=Idx(ux,uy),v=Idx(vx,vy); Ds.Merge(u,v); } int Calc(int siz){ int ret=1; for(int i=1;i<=siz;i++){ int it=-1; for(int j=i;j<=siz;j++) if(mat[j][i]){ it=j; break; } if(it==-1) return 0; if(it!=i){ ret=Sub(0,ret); for(int j=i;j<=siz;j++) swap(mat[i][j],mat[it][j]); } ret=Mul(ret,mat[i][i]); int dv=Pow(mat[i][i],MOD-2); for(int j=i;j<=siz;j++) mat[i][j]=Mul(mat[i][j],dv); for(int j=i+1;j<=siz;j++){ if(!mat[j][i]) continue; int mul=mat[j][i]; for(int k=i;k<=siz;k++) mat[j][k]=Sub(mat[j][k],Mul(mat[i][k],mul)); } } return ret; } int main(){ int cas;scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",maz[i]+1); Ds.Init(n*m+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ imap[Idx(i,j)]=-1; switch(maz[i][j]){ case 'L': Link(i,j,i,j-1);break; case 'R': Link(i,j,i,j+1);break; case 'U': Link(i,j,i-1,j);break; case 'D': Link(i,j,i+1,j);break; } } bool fai=false; for(int i=1;i<=n && !fai;i++) for(int j=1;j<=m;j++){ int it=Ds.Find(Idx(i,j)); if(it){ it--; int x=it/m+1,y=it%m+1; if(maz[x][y]!='.'){ fai=true; break; } } } if(fai){printf("0\n");continue;} int siz=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(maz[i][j]=='.'){ for(int k=0;k<4;k++){ int x=i+DIR[k][0],y=j+DIR[k][1]; int u=Idx(i,j),v=Ds.Find(Idx(x,y)); if(imap[u]==-1) imap[u]=++siz; if(imap[v]==-1) imap[v]=++siz; u=imap[u],v=imap[v]; mat[u][u]=Add(mat[u][u],1); mat[u][v]=Sub(mat[u][v],1); } } printf("%d\n",Calc(siz)); for(int i=0;i<=siz;i++) for(int j=0;j<=siz;j++) mat[i][j]=0; } return 0; }
|