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
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define SIZE(c) ((int)(c).size())
#define FT first
#define SD second
#define INT(x) int x; scanf("%d", &x)

typedef unsigned long long ULL;
typedef long double LD;
typedef vector<ULL> VULL;

const int DX[4] = {0, 1, 0, -1};
const int DY[4] = {1, 0, -1, 0};
int n, m;
typedef char A[8][9];
A a, b;

ULL enc(const A& a) {
	ULL r = 0;
	REP(i,n) REP(j,m) if (a[i][j] == 'O') r |= 1ULL << (i * m + j);
	return r;
}

bool par(ULL x) {
	bool r = 0;
	REP(i,n) REP(j,m) if (x & (1ULL << (i * m + j))) r ^= (i & 1) ^ (j ^ 1);
	return r;
}

VULL nei(ULL x) {
	VULL r;
	REP(i,n) REP(j,m) if (x & (1ULL << (i * m + j))) REP(k,4) {
		int ii = i + DX[k], jj = j + DY[k];
		if (ii >= 0 && ii < n && jj >= 0 && jj < m && !(x & (1ULL << (ii * m + jj))))
			r.PB(x ^ (1ULL << (i * m + j)) ^ (1ULL << (ii * m + jj)));
	}
	return r;
}

int main() {
	INT(n1);
	INT(m1);
	n = n1;
	m = m1;
	REP(i,n) scanf("%s", &a[i]);
	REP(i,n) scanf("%s", &b[i]);
	if (par(enc(a)) != par(enc(b))) {
		printf("0\n");
		return 0;
	}
	map<ULL, LD> p;
	p[enc(a)] = 1;
	ULL w = 0;
	REP(it,1000000) {
		map<ULL, LD> q;
		FORE(it,p) {
			VULL v = nei(it->FT);
			LD x = it->SD / SIZE(v);
			FORE(it,v) q[*it] += x;
		}
		swap(p, q);
		w += SIZE(p);
		if (w > 1000000000) break;
	}
	printf("%.15lf\n", double(p[enc(b)]));
}