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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 10;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int n, m, i, j, k, d, par, num, col[N][N], colNum[2], actNum[2], miss[2], mis, l, len, c;
LL sum, act;
char t[N];
ii kol[N * N];
vector<ii> startV, endV, ne;

bool oks(int a, int b) {
	return a >= 0 && a < n && b >= 0 && b < m;
}

bool oks(int a, int b, vector<ii>& pos) {
	if (a >= 0 && a < n && b >= 0 && b < m) {
		for (auto& w : pos) if (w.first == a && w.second == b) return false;
		return true;
	}
	return false;
}

int eval(vector<ii>& pos) {
	int res = 0;
	for (auto& w : pos) {
		for (int k=0;k<4;k++) if (oks(w.first + dx[k], w.second + dy[k], pos)) res++;
	}
	return res;
}

int evalParity(vector<ii>& pos) {
	int res = 0;
	for (auto& w : pos) res += col[w.first][w.second];
	return res % 2;
}

LL comb(int a, int b) {
	LL res = 1;
	for (int i=a;i>a-b;i--) res *= i;
	for (int i=2;i<=b;i++) res /= i;
	return res;
}

int main() {
scanf("%d %d", &n, &m);
for (i=0;i<n;i++) for (j=0;j<m;j++) {
	col[i][j] = (i + j) % 2;
	colNum[col[i][j]]++;
}

for (i=0;i<n;i++) {
	scanf("%s", t);
	for (j=0;j<m;j++) if (t[j] == 'O') startV.pb(ii(i, j));
}
for (i=0;i<n;i++) {
	scanf("%s", t);
	for (j=0;j<m;j++) if (t[j] == 'O') endV.pb(ii(i, j));
}
num = startV.size();
par = evalParity(startV);
if (par != evalParity(endV)) {
	printf("0\n");
	return 0;
}
sum = 0;
for (i=0;i<n;i++) for (j=0;j<m;j++) {
	ne.clear();
	for (k=0;k<4;k++) if (oks(i + dx[k], j + dy[k])) ne.pb(ii(i + dx[k], j + dy[k]));
	len = ne.size();
	for (k=0;k<(1<<len);k++) if (1 + __builtin_popcount(k) <= startV.size()) {
		actNum[0] = actNum[1] = 0;
		miss[0] = colNum[0];
		miss[1] = colNum[1];
		actNum[col[i][j]]++;
		miss[col[i][j]]--;
		for (l=0;l<len;l++) {
			c = col[ne[l].first][ne[l].second];
			if ((1<<l) & k) actNum[c]++;
			miss[c]--;
		}
		mis = startV.size() - 1 - __builtin_popcount(k);
		//printf(" %d %d %d\n", miss[0], miss[1], mis); 
		for (l=0;l<=mis;l++) if ((actNum[1] + l) % 2 == par && l <= miss[1] && (mis - l) <= miss[0]) {
			act = comb(miss[1], l) * comb(miss[0], mis - l) * (len - __builtin_popcount(k));
			sum += act;
		}
		//printf("%d %lld\n", k, sum);
	}
	//printf("%lld\n", sum);
	//return 0;
}
//if (n > 1 && m > 1) sum /= startV.size();
//printf("%lld\n", sum);
printf("%.15lf\n", eval(endV) * 1.0 / sum);

return 0;
}