[HEOI2015] 小Z的房间

题目链接：戳我

其实是矩阵树定理模板题。
但是要注意不合法的情况预处理的时候设置成0，要不然计算行列式的时候有问题。直接跳过不合法情况，不给它建立新点就行了。
代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000000
using namespace std;
int n,m,cnt;
long long ans=1;
char cur[20][20];
int d[110][110],a[110][110],c[110][110],trans[20][20];
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("ce.in","r",stdin);
	#endif
	scanf("%d%d",&n,&m);
	memset(a,0,sizeof(a));
	memset(d,0,sizeof(d));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>cur[i][j];
			if(cur[i][j]=='.') trans[i][j]=++cnt;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(cur[i][j]=='.')
			{
				if(i+1<=n&&cur[i+1][j]=='.') a[trans[i][j]][trans[i+1][j]]=1,d[trans[i][j]][trans[i][j]]++;
				if(i-1>=1&&cur[i-1][j]=='.') a[trans[i][j]][trans[i-1][j]]=1,d[trans[i][j]][trans[i][j]]++;
				if(j+1<=m&&cur[i][j+1]=='.') a[trans[i][j]][trans[i][j+1]]=1,d[trans[i][j]][trans[i][j]]++;
				if(j-1>=1&&cur[i][j-1]=='.') a[trans[i][j]][trans[i][j-1]]=1,d[trans[i][j]][trans[i][j]]++;
			}
	n=cnt;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			c[i][j]=d[i][j]-a[i][j];
	for(int i=2;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			while(c[j][i])
			{
				int p=c[i][i]/c[j][i];
				for(int k=i;k<=n;k++)
					c[i][k]=(c[i][k]-1ll*p*c[j][k]%mod+mod)%mod,swap(c[i][k],c[j][k]);			
				ans=-ans;
			}
	for(int i=2;i<=n;i++)
		ans=1ll*ans*c[i][i]%mod;
	printf("%lld
",(ans+mod)%mod);
	return 0;
}