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
111
112
113
114
115
116
#include <bits/stdc++.h>

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define st first
#define nd second

using namespace std;
 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vll = vector<ll>;

int n, m;
vector<string> start_board, end_board;

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

ll Choose(int n, int k) {
	ll ans = 1;
	for (int i = 0; i < k; ++i) {
		ans *= n - i;
		ans /= i + 1;
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	cerr << fixed << setprecision(6);
	
	cin >> n >> m;
	auto ReadBoard = [&](vector<string> &board) {
		board.resize(n);
		for (string &line : board) { cin >> line; }
	};
	auto GetParity = [&](const vector<string> &board) {
		int parity = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (board[i][j] == 'O') {
					parity = (parity + i + j) % 2;
				}
			}
		}
		return parity;
	};
	ReadBoard(start_board);
	ReadBoard(end_board);
	
	const int parity_start = GetParity(start_board);
	if (GetParity(end_board) != parity_start) {
		cout << "0\n";
		return 0;
	}
	
	int num_pieces = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (start_board[i][j] == 'O') { ++num_pieces; }
		}
	}
	
	ll sum_degrees = Choose(n * m - 2, num_pieces - 1);
	sum_degrees *= (n * (m - 1) + m * (n - 1));
	
	int end_degree = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (end_board[i][j] != 'O') { continue; }
			for (int d = 0; d < 4; ++d) {
				const int ni = i + dr[d];
				const int nj = j + dc[d];
				if (ni < 0 || nj < 0 || ni >= n || nj >= m) { continue; }
				if (end_board[ni][nj] != '.') { continue; }
				++end_degree;
			}
		}
	}
	
	cout << (long double)end_degree / sum_degrees << "\n";
}