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
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; i >= a; i--)
#define cat(x) cout << #x << ": " << x << endl

using namespace std;
using ll = long long;

const int N = 8;

int n, m;
long long dp1[1 << N][N + 1][4 * N + 1][2];
long long dp2[1 << N][N + 1][4 * N + 1][2];
long long sum[4 * N + 1];
char s[N][N];

array<int, 2> read() {
	array<int, 2> p = {0, 0};
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		for (int j = 0; j < m; j++) {
			if (s[i][j] == 'O') {
				p[(i + j) % 2]++;
			}
		}
	}
	return p;
}

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

	cin >> n >> m;
	auto p1 = read();
	auto p2 = read();

	if (p1[0] % 2 != p2[0] % 2) {
		cout << "0\n";
		return 0;
	}

	int cnt = p1[0] + p1[1];

	auto bit = [&](int mask, int k) {
		return mask >> k & 1;
	};

	dp1[0][0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			memset(dp2, 0, sizeof dp2);
			for (int mask = 0; mask < (1 << m); mask++) {
				for (int c = 0; c <= cnt; c++) {
					for (int moves = 0; moves <= 4 * cnt; moves++) {
						for (int par = 0; par < 2; par++) {
							if (c < cnt) {
								int mask2 = mask | 1 << j;
								int c2 = c + 1;
								int moves2 = moves + (j > 0 && !bit(mask, j - 1)) + (i > 0 && !bit(mask, j));
								int par2 = par ^ ((i + j) % 2);
								dp2[mask2][c2][moves2][par2] += dp1[mask][c][moves][par];
							}
							int mask2 = mask & (-1 - (1 << j));
							int c2 = c;
							int moves2 = moves + (j > 0 && bit(mask, j - 1)) + (i > 0 && bit(mask, j));
							int par2 = par;
							dp2[mask2][c2][moves2][par2] += dp1[mask][c][moves][par];
						}
					}
				}
			}
			memcpy(dp1, dp2, sizeof dp1);
		}
	}

	for (int mask = 0; mask < (1 << m); mask++) {
		for (int moves = 0; moves <= 4 * cnt; moves++) {
			sum[moves] += dp1[mask][cnt][moves][p1[0] % 2];
		}
	}

	long long value = 0;
	for (int moves = 0; moves <= 4 * cnt; moves++) {
		value += moves * sum[moves];
	}

	int moves = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] == 'O') {
				vector<pair<int, int>> dir = {{0, -1}, {0, +1}, {-1, 0}, {+1, 0}};
				for (auto [di, dj] : dir) {
					int ni = i + di;
					int nj = j + dj;
					if (0 <= ni && ni < n && 0 <= nj && nj < m && s[ni][nj] == '.') {
						moves++;
					}
				}
			}
		}
	}

	cout << setprecision(15) << fixed << (double) moves / value << "\n";

	return 0;
}