URAL 1627

• .:卧室,*:储藏间.给相邻的卧室建边,看有多少种连接所有卧室的方法,
• 生成树计数

  #include <iostream>
  #include <algorithm>
  #include <string.h>
  #include <math.h>
  #define ll long long 
  #define mod 1000000000
  using namespace std;
  const int inf = 0x3f3f3f3f;
  const int maxn = 105;
  ll b[maxn][maxn];
  char e[10][10];
  int id[10][10];
  int n, m;
  // 学过线代都知道求行列式的方法之一就是化成上\下三脚矩阵,对角线元素乘积是行列式值
  ll determina(int n) {
  	ll res = 1;
  	for (int i = 1; i <= n; i++) {
  		if (!b[i][i]) { //若果对角线元素为0,把此行都一都移到下一行去
  			bool flag = false;
  			for (int j = i + 1; j <= n; j++) { //从i+1行开始找i列中的第一个不为0的元素，与现在的行交换
  				if (b[j][i]) {//找到了该列不为0的元素,
  					flag = 1; //标记,交换
  					for (int k = i; k <= n; k++) swap(b[i][k], b[j][k]);
  					res = -res;// 换行系数变为负数
  					break; //退出.
  				}
  			}
  			if (!flag) return 0; //这一行全部为0,行列式值为0
  		}
  
  		for (int j = i + 1; j <= n; j++) {
  			while (b[j][i]) { //从下面的行找一个不为0的元素与第i行进行消元
  				ll t = b[i][i] / b[j][i];
  				for (int k = i; k <= n; k++) {
  					b[i][k] = (b[i][k] - t * b[j][k]) % mod;
  					swap(b[i][k], b[j][k]);//消元后,把0的行换到下面来。
  				}
  				res = -res;
  			}
  		}
  		res *= b[i][i];//对角线元素相乘
  		res %= mod;
  	}
  	return (res + mod) % mod;
  }
  int next1[4][2] = {0,1,1,0,0,-1,-1,0};
  bool istrue(int x,int y) {
  	if (x >= 1 && y >= 1 && x <= n && y <= m) return 1;
  	else return 0;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	while (scanf("%d%d",&n,&m) != EOF) {
  		memset(b, 0, sizeof b);
  		memset(id,0,sizeof id);
  		int cnt = 0;
  		for (int i = 1; i <= n; i++) {
  			scanf("%s",e[i]+1);
  			for (int j = 1; j <= m; j++) 
  				if (e[i][j] == '.') 
  					id[i][j] = ++cnt; 		
  		}
  		for (int i = 1; i <= n; i++) {
  			for (int j = 1; j <= m; j++) {
  				if (e[i][j] == '.') {
  					int u = id[i][j], v;
  					for (int k = 0; k < 4; k++) {
  						int tx = i + next1[k][0];
  						int ty = j + next1[k][1];
  						if (istrue(tx, ty) && e[tx][ty] == '.') {
  							v = id[tx][ty];
  							b[u][u]++; b[u][v] = -1;
  						}
  					}
  				}
  			}
  		}
  		n = cnt-1; // n-1阶子式子 
  		printf("%lld\n",determina(n));
  	}
  	return 0;
  }