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
#include<bits/stdc++.h>
using namespace std;
using lld = long long;

const int MAXN = 8;

lld sum[MAXN+1][MAXN+1][1<<MAXN];
lld cnt[MAXN+1][MAXN+1][1<<MAXN];

lld deg(int n, int m, const string& s) {
	int res = 0;
	for(int i=0;i<s.length();i++) {
		int x = i/m, y = i%m;
		if(s[i] == '.') {
			if(x-1 >= 0 && s[i-m] == 'O') res++;
			if(x+1 < n && s[i+m] == 'O') res++;
			if(y-1 >= 0 && s[i-1] == 'O') res++;
			if(y+1 < m && s[i+1] == 'O') res++;
		}
	}
	return res;
}

inline int count(int x) { return __builtin_popcount(x); }

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);

	int n,m;
	cin >> n >> m;

	vector<string> t(n);
	for(auto& i : t)
		cin >> i;

	vector<string> r(n);
	for(auto& i : r)
		cin >> i;

	int x = 0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) {
			if(t[i][j] == 'O')
				x += i+j;
			if(r[i][j] == 'O')
				x += i+j;
		}

	if(x%2 == 1) {
		cout << "0\n";
		return 0;
	}

	int k=0;
	string R = "";
	for(auto i : r)
		R += i;
	for(char c : R)
		if(c == 'O') k++;

	auto horizontal = [=](int x) {
		int res = 0;
		for(int i=0;i<m-1;i++) {
			if((x&(1<<i)) && !(x&(1<<(i+1)))) res++;
			if(!(x&(1<<i)) && (x&(1<<(i+1)))) res++;
		}
		return res;
	};

	auto vertical = [=](int x, int y) {
		return count(x^y);
	};

	for(int i=0;i<(1<<m);i++) {
		sum[0][count(i)][i] = horizontal(i);
		cnt[0][count(i)][i] = 1;
	}

	for(int i=1;i<n;i++)
		for(int l=0;l<=k;l++)
			for(int p=0;p<(1<<m);p++)
				if(count(p) <= l)
					for(int q=0;q<(1<<m);q++)
						if(l+count(q) <= k) {
							sum[i][l+count(q)][q] += sum[i-1][l][p];
							sum[i][l+count(q)][q] += cnt[i-1][l][p] * (horizontal(q) + vertical(p,q));
							cnt[i][l+count(q)][q] += cnt[i-1][l][p];
						}

	lld S = 0;
	for(int q=0;q<(1<<m);q++)
		S += sum[n-1][k][q];
	S /= 2;
	lld D = deg(n,m,R);
	cout << (long double) D / S << "\n";

	return 0;
}