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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 10, S = 100;
int n, m, a[N][N], b[N][N];
i64 c[S][S];
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i <= n * m; i ++) {
		c[i][0] = 1;
		for(int j = 1; j <= i; j ++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}
	for(int i = 1; i <= n; i ++) {
		string str; cin >> str; str = "?" + str;
		for(int j = 1; j <= m; j ++) {
			a[i][j] = str[j] == 'O' ? 1 : 0;

		}
	}
	for(int i = 1; i <= n; i ++) {
		string str; cin >> str; str = "?" + str;
		for(int j = 1; j <= m; j ++) {
			b[i][j] = str[j] == 'O' ? 1 : 0;
		}
	}
	array<int, 2> cnt{0, 0};
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) cnt[i + j & 1] ++;
	}
	int xa = 0, xb = 0, cnta = 0, cntb = 0;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) if(i + j & 1) xa ^= a[i][j], xb ^= b[i][j];
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) cnta += a[i][j], cntb += b[i][j];
	}
	cout << fixed << setprecision(14);
	if(xa != xb || cnta != cntb) {
		cout << 0.0 << '\n';
		return 0;
	}
	long double sum = 0;
	cnt[0] --, cnt[1] --, cnta --;
	for(int i = 0; i <= cnt[1] && i <= cnta; i ++) {
		if(cnta - i <= cnt[0]) {
			sum += c[cnt[1]][i] * c[cnt[0]][cnta - i];
		}
	}
	sum *= (n - 1) * m + n * (m - 1);
	long double cur = 0;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			if(i != n) cur += b[i][j] != b[i + 1][j];
			if(j != m) cur += b[i][j] != b[i][j + 1];
		}
	}
	cout << cur / sum << '\n';
	return 0;
}