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
#include <bits/stdc++.h>
#ifdef LOC
#include "debuglib.h"
#else
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   vi         = vector<int>;
using   pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

using dbl = long double;

struct Transition {
	int pieces, moves, mask;
};

// row count, piece count, move count, last row -> configuration count
ll dp[9][9][33][256];
vector<Transition> trans[256];

pii check(const vector<string>& mat) {
	int parity = 0, moves = 0;
	rep(i, 0, sz(mat)) {
		rep(j, 0, sz(mat[i])) {
			if (mat[i][j] == 'O') {
				parity += i+j;
				moves += (i > 0 && mat[i-1][j] == '.');
				moves += (j > 0 && mat[i][j-1] == '.');
				moves += (i+1 < sz(mat) && mat[i+1][j] == '.');
				moves += (j+1 < sz(mat[0]) && mat[i][j+1] == '.');
			}
		}
	}
	return {parity%2, moves};
}

void run() {
	int n, m;
	cin >> n >> m;

	vector<string> from(n), to(n);
	each(r, from) cin >> r;
	each(r, to) cin >> r;

	pii pFrom = check(from);
	pii pTo = check(to);

	if (pFrom.x != pTo.x) {
		cout << 0.0 << '\n';
		return;
	}

	int k = 0;
	each(r, from) k += int(count(all(r), 'O'));

	rep(dst, 0, 1<<m) {
		Transition t;
		t.pieces = __builtin_popcount(dst);
		t.moves = __builtin_popcount((dst ^ (dst >> 1)) & ((1 << (m-1)) - 1));
		t.mask = dst;
		rep(src, 0, 1<<m) {
			if (t.pieces + __builtin_popcount(src) > k) continue;
			Transition s = t;
			s.moves += __builtin_popcount(src ^ dst);
			trans[src].pb(s);
		}
		dp[1][t.pieces][t.moves][dst] = 1;
	}

	rep(row, 1, n) {
		rep(pieces, 0, k+1) {
			rep(moves, 0, pieces*4+1) {
				rep(mask, 0, 1<<m) {
					each(t, trans[mask]) {
						int newPieces = pieces + t.pieces;
						int newMoves = moves + t.moves;
						if (newPieces <= k && newMoves <= k*4) {
							dp[row+1][newPieces][newMoves][t.mask] += dp[row][pieces][moves][mask];
						}
					}
				}
			}
		}
	}

	ll inv = 0;
	rep(moves, 1, k*4+1) {
		rep(mask, 0, 1<<m) {
			inv += dp[n][k][moves][mask] * moves;
		}
	}

	assert(inv%2 == 0);
	inv /= 2;

	dbl ans = dbl(pTo.y) / dbl(inv);
	cout << ans << '\n';
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(16);
	run();
	cout << flush; _Exit(0);
}