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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ldb;
typedef pair<int,int> pii;
const int MAXN = 8 + 5;
const int ALL = (1<<8) + 5;

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)

tuple<int,int,int> calc(char s[MAXN][MAXN], int n, int m)
{
	int x = 0, y = 0, z = 0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
		{
			if(s[i][j] == 'O')
				++x, y += i + j;
			if(i+1 <= n && s[i][j] != s[i+1][j])
				++z;
			if(j+1 <= m && s[i][j] != s[i][j+1])
				++z;
		}
	y %= 2;
	return make_tuple(x,y,z);
}

char a[MAXN][MAXN], b[MAXN][MAXN];

int main(void)
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i)
		scanf("%s",a[i]+1);
	for(int i=1; i<=n; ++i)
		scanf("%s",b[i]+1);
	
	auto beg = calc(a, n, m), enn = calc(b, n, m);
	if(get<0>(beg) != get<0>(enn) || get<1>(beg) != get<1>(enn))
	{
		printf("0\n");
		return 0;
	}
	
	int d = get<0>(beg);
	int all = (1<<m) - 1;
	
	static ll dp[2][ALL][MAXN][2][2];// {ways, sum}
	int now = 0;
	dp[now][0][0][0][0] = 1;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
		{
			now ^= 1;
			memset(dp[now], 0, sizeof(dp[now]));
			
			for(int mask=0; mask<=all; ++mask)
				for(int x=0; x<=d; ++x)
					for(int y=0; y<=1; ++y) if(dp[now^1][mask][x][y][0])
					{
						for(int use=0; use<=1; ++use)
						{
							if(x + use > d) continue;
							
							int nxt = (mask & ~bbit(j-1)) | use << (j-1);
							int xx = x + use;
							int yy = y ^ (use? (i + j) % 2: 0);
							int more = 0;
							if(j > 1 && use != bdig(mask, j-2)) ++more;
							if(i > 1 && use != bdig(mask, j-1)) ++more;
							
							dp[now][nxt][xx][yy][0] += dp[now^1][mask][x][y][0];
							dp[now][nxt][xx][yy][1] += dp[now^1][mask][x][y][1] + dp[now^1][mask][x][y][0] * more;
						}
					}
		}
	
	ll sum = 0;
	for(int mask=0; mask<=all; ++mask)
		sum += dp[now][mask][d][get<1>(beg)][1];
	
	double ans = (double)get<2>(enn) / sum;
	printf("%.15lf\n",ans);
	return 0;
}