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
#include <cstdio>

const int N = 8;
const int M = 1 << N;
long long d[N + 1][M][N * 4 + 1][N + 1][2], freq[N * 4 + 1];
int n, m, dcnt[M][M], pi, f[2][M];
char s[N][N + 1];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < 1 << m; ++i) for (int j = 0; j < 2; ++j) for (int k = j; k < m; k += 2) f[j][i] = f[j][i] + (i >> k) & 1;
	int np = 0, after = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%s", s[i]);
		int mask = 0;
		for (int j = 0; j < m; ++j) if (s[i][j] == 'O') {
			++pi;
			mask |= 1 << j;
		}
		np ^= f[i & 1][mask];
	}
	for (int i = 0; i < 1 << m; ++i) {
		for (int j = 0; j < 1 << m; ++j) {
			for (int k = 0; k < m; ++k) {
				if (j >> k & 1) {
					dcnt[i][j] += i >> k & 1 ^ 1;
					dcnt[i][j] += k && j >> k - 1 & 1 ^ 1;
					dcnt[i][j] += k + 1 < m && j >> k + 1 & 1 ^ 1;
				}
				dcnt[i][j] += j >> k & 1 ^ 1 && i >> k & 1;
			}
		}
	}
	d[0][0][0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 1 << m; ++j) {
			for (int free = 0; free <= 4 * pi; ++free) {
				for (int licz = 0; licz <= pi; ++licz) {
					for (int par = 0; par < 2; ++par) if (d[i][j][free][licz][par]) {
						long long cur = d[i][j][free][licz][par];
						if (cur) for (int k = 0; k < 1 << m; ++k) {
							int licz1 = licz + __builtin_popcount(k);
							if (licz1 <= pi) d[i + 1][k][free + dcnt[j][k] - (i ? 0 : __builtin_popcount(k))][licz1][par ^ f[i & 1][k]] += cur;
						}
					}
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		scanf("%s", s[i]);
		int mask = 0;
		for (int j = 0; j < m; ++j) mask |= (s[i][j] == 'O') << j;
		after ^= f[i & 1][mask];
	}
	if (np != after) {
		printf("0\n");
		return 0;
	}
	int flicz = 0, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) if (s[i][j] == 'O') {
			for (int dir = 0; dir < 4; ++dir) {
				int x1 = i + dx[dir], y1 = j + dy[dir];
				if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && s[x1][y1] == '.') ++flicz;
			}
		}
	}
	for (int i = 0; i <= 4 * pi; ++i) for (int j = 0; j < 1 << m; ++j) freq[i] += d[n][j][i][pi][np];
	long long s = 0;
	for (int i = 0; i <= 4 * pi; ++i) freq[i] *= i;
	for (int i = 0; i <= 4 * pi; ++i) s += freq[i];
	printf("%.15lf\n", (double)flicz / s);
	return 0;
}