loj6259「CodePlus 2017 12 月赛」白金元首与独舞

分析

我们将没连的点连向周围四个点

其余的按照给定的方向连

我们将所有连出去的位置统一连到0点上

再以0作为树根

于是就将问题转化为了有向图内向树计数

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int mod = 1e9+;

const int dx[] = {,-,,};

const int dy[] = {,,,-};

int n,m,g[][],id[][],cnt,ok;

char s[][];

inline void add(int x,int y){

    g[y][y]++;

    g[y][x]--;

}

inline int dfs(int x, int y, int len) {

    if(x<||x>n||y<||y>m)return ;

    if(id[x][y]!=-)return id[x][y];

    if(len>n*m){

      ok=;

      return ;

    }

    if(s[x][y]=='L')return id[x][y]=dfs(x,y-,len+);

    if(s[x][y]=='R')return id[x][y]=dfs(x,y+,len+);

    if(s[x][y]=='U')return id[x][y]=dfs(x-,y,len+);

    if(s[x][y]=='D')return id[x][y]=dfs(x+,y,len+);

}

inline int gs(){

    int i,j,k,ans=;

    for(i=;i<=cnt;i++)

      for(j=;j<=cnt;j++)

        g[i][j]=(g[i][j]%mod+mod)%mod;

    for(i=;i<=cnt;i++){

      for(j=i;j<=cnt;j++)

        if(g[i][j])break;

      if(j>cnt)return ;

      if(j!=i)ans=mod-ans,swap(g[i],g[j]);

      for(j=i+;j<=cnt;j++){

          while(g[j][i]){

            int t=g[i][i]/g[j][i];

            for(k=i;k<=cnt;k++)

              g[i][k]=(g[i][k]-1ll*t*g[j][k]%mod+mod)%mod;

            ans=mod-ans;

            swap(g[i],g[j]);

          }

      }

      ans=1ll*ans*g[i][i]%mod;

    }

    return ans;

}

inline void solve(){

    int i,j,k;

    ok=;

    cnt=;

    memset(g,,sizeof(g));

    memset(id,-,sizeof(id));

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++)scanf("%s",s[i]+);

    for(i=;i<=n;i++)

      for(j=;j<=m;j++)

        if(s[i][j]=='.')

          id[i][j]=++cnt;

    for(i=;i<=n;i++)

      for(j=;j<=m;j++)

        if(s[i][j]=='.'){

          for(k=;k<;k++)

            add(dfs(i+dx[k],j+dy[k],),id[i][j]);

        }else dfs(i,j,);

    if(ok){

      puts("");

      return;

    }

    printf("%d\n",gs());

    return;

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--)solve();

    return ;

}