1627. Join
Time limit: 4.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Businessman Petya recently bought a new house. This house has one floor withn ×m square rooms, placed in rectangular lattice. Some rooms are pantries and the other ones are bedrooms. Now he wants
to join all bedrooms with doors in such a way that there will be exactly one way between any pair of them. He can make doors only between neighbouring bedrooms (i.e. bedrooms having a common wall). Now he wants to count the number of different ways he can
do it.
to join all bedrooms with doors in such a way that there will be exactly one way between any pair of them. He can make doors only between neighbouring bedrooms (i.e. bedrooms having a common wall). Now he wants to count the number of different ways he can
do it.
Input
First line contains two integers n and
m(1 ≤ n, m ≤ 9) — the number of lines and columns in the lattice. Nextn lines contain exactlym characters representing house map, where "." means bedroom and "*" means pantry. It is guaranteed that there
is at least one bedroom in the house.
m
is at least one bedroom in the house.
Output
Output the number of ways to join bedrooms modulo 109.
Samples
| input | output |
|---|---|
2 2 .. .. |
4 |
2 2 *. .* |
0 |
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
Tags:
)
Difficulty: 1154 Printable version Submit
solution Discussion (13)
All submissions (1680) All accepted submissions (428)
Solutions rating (223)
solution Discussion (13)
All submissions (1680) All accepted submissions (428)
Solutions rating (223)
还是用拉普拉斯矩阵, 消元时用类似辗转相除的办法,保证中间过程为整数
/*************************************************************************
> File Name: st10.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> Created Time: 2015年01月29日 星期四 16时22分40秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
const int N = 210;
const int mod = 1000000000;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
char str[20][20];
int ord[N];
LL mat[N][N];
LL Det (int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
mat[i][j] %= mod;
}
}
LL res = 1;
for (int i = 0; i < n; ++i)
{
if (!mat[i][i])
{
bool flag = false;
for (int j = i + 1; j < n; ++j)
{
if (mat[j][i])
{
flag = true;
for (int k = i; k < n; ++k)
{
swap (mat[i][k], mat[j][k]);
}
res = -res;
break;
}
}
if (!flag)
{
return 0;
}
}
for (int j = i + 1; j < n; ++j)
{
while (mat[j][i])
{
LL t = mat[i][i] / mat[j][i];
for (int k = i; k < n; ++k)
{
mat[i][k] = (mat[i][k] - t * mat[j][k]) % mod;
swap (mat[i][k], mat[j][k]);
}
res = -res;
}
}
res = (res * mat[i][i]) % mod;
}
return (res + mod) % mod;
}
int main()
{
int n, m;
while (~scanf("%d%d", &n, &m))
{
int cnt = 0;
memset (mat, 0, sizeof(mat));
for (int i = 0; i < n; ++i)
{
scanf("%s", str[i]);
for (int j = 0; j < m; ++j)
{
if (str[i][j] == '.')
{
ord[i * m + j] = cnt++;
}
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (str[i][j] == '.')
{
for (int k = 0; k < 4; ++k)
{
int x = i + dir[k][0];
int y = j + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= m || str[x][y] != '.')
{
continue;
}
mat[ord[i * m + j]][ord[x * m + y]] = -1;
}
}
}
}
for (int i = 0; i < cnt; ++i)
{
LL ret = 0;
for (int j = 0; j < cnt; ++j)
{
if (i != j && mat[i][j])
{
++ret;
}
}
mat[i][i] = ret;
}
LL ans = Det(cnt - 1);
printf("%lld\n", ans);
}
return 0;
}