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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // University of Warsaw
using LL = long long;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())
ostream& operator<<(ostream &o, string s);
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p);
template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
	o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}';
}
ostream& operator<<(ostream &o, string s) {
	return o << s.data();
}
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) {
	return o << '(' << p.first << ", " << p.second << ')';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

mt19937 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

LL choose(int n, int k) {
	if(n < k)
		return 0;
	LL ret = 1;
	REP(i, k)
		ret *= n - i;
	REP(i, k)
		ret /= i + 1;
	debug(n, k, ret);
	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m;
	cin >> n >> m;
	vector<string> in(n, string(m, '.'));
	int k = 0, initial_parity = 0;
	REP(y, n)
		REP(x, m) {
			cin >> in[y][x];
			if(in[y][x] == 'O') {
				++k;
				initial_parity ^= (x + y) % 2;
			}
		}
	debug(n, m, k, initial_parity);

	LL sum_cnt_free_neighbors = 0;
	REP(x, m)
		REP(y, n)
			REP(s, 4) {
				int xx = x + array<int, 4>{{0, 1, 0, -1}}[s];
				int yy = y + array<int, 4>{{1, 0, -1, 0}}[s];
				if(0 <= xx and xx < m and 0 <= yy and yy < n) {
					int other0 = 0, other1 = 0;
					REP(x0, m)
						REP(y0, n)
							if(pair(x0, y0) != pair(x, y) and pair(x0, y0) != pair(xx, yy))
								((x0 + y0) % 2 == 1 ? other1 : other0) += 1;
					int goal_parity = initial_parity ^ ((x + y) % 2);
					debug(x, y, xx, yy, other0, other1, goal_parity);
					LL ways = 0;
					FOR(using0, 0, other0)
						FOR(using1, 0, other1)
							if(1 + using0 + using1 == k and using1 % 2 == goal_parity) {
								debug(using0, using1);
								ways += choose(other0, using0) * choose(other1, using1);
							}
					debug(x, y, xx, yy, ways);
					sum_cnt_free_neighbors += ways;
				}
			}
	debug(sum_cnt_free_neighbors);

	vector<string> out(n, string(m, '.'));
	int ending_parity = 0, ending_neighbor_cnt = 0;
	REP(y, n)
		REP(x, m)
			cin >> out[y][x];
	REP(y, n)
		REP(x, m) {
			if(out[y][x] == 'O') {
				ending_parity ^= (x + y) % 2;
				REP(s, 4) {
					int xx = x + array<int, 4>{{0, 1, 0, -1}}[s];
					int yy = y + array<int, 4>{{1, 0, -1, 0}}[s];
					if(0 <= xx and xx < m and 0 <= yy and yy < n and out[yy][xx] == '.')
						++ending_neighbor_cnt;
				}
			}
		}
	if(ending_parity != initial_parity) {
		cout << "0\n";
		return 0;
	}

	using LD = long double;
	cout << setprecision(17) << fixed;
	cout << LD(ending_neighbor_cnt) / LD(sum_cnt_free_neighbors) << '\n';
}