1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #define REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = binn(a, b)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 100 + 5, maxm = 180000 + 10, inf = 1e9, MOD = 20110520;
int n, m, N;
int bin[25];
char mp[maxn][maxn];
int f[maxm], g[maxm];
inline int w(int x, int y) {return x / bin[y] % 3;}
inline int s(int x, int y, int z) {return x - w(x, y) * bin[y] + z * bin[y];}
int main()
{
#ifdef CraZYali
freopen("2331.in", "r", stdin);
freopen("2331.out", "w", stdout);
#endif
bin[0] = 1;
REP(i, 1, 20) bin[i] = bin[i-1] * 3;
cin >> n >> m;
REP(i, 1, n) scanf("%s", mp[i] + 1);
if (n < m)
{
REP(i, 1, n)
REP(j, i, m) swap(mp[i][j], mp[j][i]);
swap(n, m);
}
f[0] = 1;
N = bin[m+1];
REP(i, 1, n)
{
REP(j, 1, m)
{
memset(g, 0, sizeof(g));
if (mp[i][j] == '*')
REP(k, 0, N - 1) g[k] += (!w(k, j-1) && !w(k, j)) * f[k];
else
REP(k, 0, N - 1)
{
if (!f[k]) continue ;
int x(w(k, j-1)), y(w(k, j));
if (!x)
if (!y)
{
(g[s(s(k, j-1, 1), j, 0)] += f[k]) %= MOD;
(g[s(s(k, j-1, 0), j, 1)] += f[k]) %= MOD;
(g[s(s(k, j-1, 2), j, 2)] += f[k]) %= MOD;
}
else if (y == 1)
{
(g[s(s(k, j-1, 1), j, 0)] += f[k]) %= MOD;
(g[s(s(k, j-1, 0), j, 2)] += f[k]) %= MOD;
}
else
{
(g[s(s(k, j-1, 0), j, 0)] += f[k]) %= MOD;
(g[s(s(k, j-1, 2), j, 0)] += f[k]) %= MOD;
}
else if (x == 1)
{
if (!y)
{
(g[s(s(k, j-1, 0), j, 1)] += f[k]) %= MOD;
(g[s(s(k, j-1, 2), j, 0)] += f[k]) %= MOD;
}
else if (y == 1) (g[s(s(k, j-1, 0), j, 0)] += f[k]) %= MOD;
}
else if (!y)
{
(g[s(s(k, j-1, 0), j, 2)] += f[k]) %= MOD;
(g[s(s(k, j-1, 0), j, 0)] += f[k]) %= MOD;
}
}
copy(g, g + sizeof(g) / sizeof(g[0]), f);
}
memset(g, 0, sizeof(g));
REP(k, 0, bin[m] - 1) g[k*3] = f[k];
copy(g, g + sizeof(g) / sizeof(g[0]), f);
}
cout << f[0] << endl;
return 0;
}
|
