【BZOJ4031】小Z的房间

  据说数据有非法字符，exited，成功爆了我的读入。

  Matrix-Tree定理，算行列式时消元用辗转相除法。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn=12,mo=1000000000;
inline char readchar() {char ch;while (!((ch=getchar())=='.' || ch=='*'));return ch;}

struct Matrix
{
	int a[maxn*maxn][maxn*maxn];
	int n;

	int* operator[] (int x) {return a[x];}

	int det()
	{
		int ans=1;
		for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=(a[i][j]%mo+mo)%mo;
		for (int i=1;i<n;i++)
		{
			for (int j=i+1;j<=n;j++) while (a[j][i])
			{
				int x=a[i][i]/a[j][i];
				for (int k=i;k<=n;k++) a[i][k]=(a[i][k]-1ll*x*a[j][k]%mo+mo)%mo;
				for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);
				ans=-ans;
			}
		}
		if (ans==-1) ans+=mo;
		for (int i=1;i<=n;i++) ans=1ll*ans*a[i][i]%mo;
		return ans;
	}
}M;

int id[maxn][maxn],ids;
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (readchar()=='.') id[i][j]=++ids;
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (id[i][j])
	{
		if (i>1 && id[i-1][j]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i-1][j]]=-1;
		if (i<n && id[i+1][j]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i+1][j]]=-1;
		if (j>1 && id[i][j-1]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i][j-1]]=-1;
		if (j<m && id[i][j+1]) M[id[i][j]][id[i][j]]++,M[id[i][j]][id[i][j+1]]=-1;
	}
	M.n=ids-1;
	printf("%d\n",M.det());
	return 0;
}