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
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll prep[9][9][9] = {{{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}},{{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0,0},{0,2,2,0,0,0,0,0,0},{0,3,6,3,0,0,0,0,0},{0,4,12,12,4,0,0,0,0},{0,5,20,30,20,5,0,0,0},{0,6,30,60,60,30,6,0,0},{0,7,42,105,140,105,42,7,0}},{{0,0,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0,0},{0,4,8,4,0,0,0,0,0},{0,7,28,42,28,7,0,0,0},{0,10,60,150,200,150,60,10,0},{0,13,104,364,728,910,728,364,104},{0,16,160,720,1920,3360,4032,3360,1920},{0,19,228,1254,4180,9405,15048,17556,15048},{0,22,308,2002,8008,22022,44044,66066,75504}},{{0,0,0,0,0,0,0,0,0},{0,2,2,0,0,0,0,0,0},{0,7,28,42,28,7,0,0,0},{0,12,84,252,420,420,252,84,12},{0,17,170,765,2040,3570,4284,3570,2040},{0,22,286,1716,6292,15730,28314,37752,37752},{0,27,432,3240,15120,49140,117936,216216,308880},{0,32,608,5472,31008,124032,372096,868224,1612416},{0,37,814,8547,56980,270655,974358,2760681,6310128}},{{0,0,0,0,0,0,0,0,0},{0,3,6,3,0,0,0,0,0},{0,10,60,150,200,150,60,10,0},{0,17,170,765,2040,3570,4284,3570,2040},{0,24,336,2184,8736,24024,48048,72072,82368},{0,31,558,4743,25296,94860,265608,575484,986544},{0,38,836,8778,58520,277970,1000692,2835294,6480672},{0,45,1170,14625,117000,672750,2960100,10360350,29601000},{0,52,1560,22620,211120,1425060,7410312,30876300,105861600}},{{0,0,0,0,0,0,0,0,0},{0,4,12,12,4,0,0,0,0},{0,13,104,364,728,910,728,364,104},{0,22,286,1716,6292,15730,28314,37752,37752},{0,31,558,4743,25296,94860,265608,575484,986544},{0,40,920,10120,70840,354200,1345960,4037880,9806280},{0,49,1372,18522,160524,1003275,4815720,18460260,58017960},{0,58,1914,30624,316448,2373360,13765488,64238944,247778784},{0,67,2546,47101,565212,4945605,33630114,184965627,845557152}},{{0,0,0,0,0,0,0,0,0},{0,5,20,30,20,5,0,0,0},{0,16,160,720,1920,3360,4032,3360,1920},{0,27,432,3240,15120,49140,117936,216216,308880},{0,38,836,8778,58520,277970,1000692,2835294,6480672},{0,49,1372,18522,160524,1003275,4815720,18460260,58017960},{0,60,2040,33660,359040,2782560,16695360,80694240,322776960},{0,71,2840,55380,701480,6488690,46718568,272524980,1323692760},{0,82,3772,84870,1244760,13381170,112401828,768079158,4389023760}},{{0,0,0,0,0,0,0,0,0},{0,6,30,60,60,30,6,0,0},{0,19,228,1254,4180,9405,15048,17556,15048},{0,32,608,5472,31008,124032,372096,868224,1612416},{0,45,1170,14625,117000,672750,2960100,10360350,29601000},{0,58,1914,30624,316448,2373360,13765488,64238944,247778784},{0,71,2840,55380,701480,6488690,46718568,272524980,1323692760},{0,84,3948,90804,1362060,14982660,128850876,901956132,5282885916},{0,97,5238,138807,2405988,30676347,306763470,2505235005,17178754320}},{{0,0,0,0,0,0,0,0,0},{0,7,42,105,140,105,42,7,0},{0,22,308,2002,8008,22022,44044,66066,75504},{0,37,814,8547,56980,270655,974358,2760681,6310128},{0,52,1560,22620,211120,1425060,7410312,30876300,105861600},{0,67,2546,47101,565212,4945605,33630114,184965627,845557152},{0,82,3772,84870,1244760,13381170,112401828,768079158,4389023760},{0,97,5238,138807,2405988,30676347,306763470,2505235005,17178754320},{0,112,6944,211792,4235840,62478640,724752224,6885146128,55081169024}}};
char wej[9][9];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	int k = 0, parz1 = 0, parz2 = 0;
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
	{
		char c;
		cin >> c;
		if(c == 'O') ++k, parz1 ^= (i&1)^(j&1);
	}
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
	{
		cin >> wej[i][j];
		if(wej[i][j] == 'O') parz2 ^= (i&1)^(j&1);
	}
	
	if(parz1 != parz2)
	{
		cout << 0;
		return 0;
	}
	
	ll licz = 0ll;
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(wej[i][j] == 'O')
	{
		if(i && wej[i-1][j]=='.') ++licz;
		if(j && wej[i][j-1]=='.') ++licz;
		if(i+1<n && wej[i+1][j]=='.') ++licz;
		if(j+1<m && wej[i][j+1]=='.') ++licz;
	}
	ll mian = prep[n][m][k];
	
	long double wyn = ((long double)licz)/((long double)mian);
	cout << setprecision(15) << fixed << wyn;
	return 0;
}

// generatorka tablicy prep
/*
#include <bits/stdc++.h>
#define ll long long
#define pll pair <ll, ll>
#define fi first
#define se second
using namespace std;

pll dp[9][9][256][2];// [a][b][c] {mozliwosci, suma dostepych ruchow} dla planszy mxa, b=pionki, c=maska ostatniego wiersza, d=parzystosc sumy wspolrzednych

int main()
{
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	
	cout << "{";
	for(int n = 0; n <= 8; ++n)
	{
		cout << "{";
		for(int m = 0; m <= 8; ++m)
		{
			cout << "{";
			for(int k = 0; k <= 8; ++k)
			{
				if(!n || !m || !k || k>n*m-1)
				{
					cout << "0";
					if(k < 8) cout << ",";
					continue;
				}
				
				for(int a = 0; a < 9; ++a) for(int b = 0; b < 9; ++b) for(int c = 0; c < 256; ++c) dp[a][b][c][0] = dp[a][b][c][1] = {0ll, 0ll};
				
				dp[0][0][0][0] = {1ll, 0ll};
				for(int a = 0; a < n; ++a) for(int b = 0; b <= k; ++b) for(int c = 0; c < (1<<m); ++c) for(int d = 0; d < 2; ++d)
				{
					for(int t = 0; t < (1<<m); ++t)
					{
						int ile = __builtin_popcount(t);
						if(b+ile > k) continue;
						
						ll dodaj = 0ll;
						if(a) for(int i = 0; i < m; ++i) if((bool)(c&(1<<i)) != (bool)(t&(1<<i))) ++dodaj;
						for(int i = 1; i < m; ++i) if((bool)(t&(1<<i)) != (bool)(t&(1<<(i-1)))) ++dodaj;
						
						int parz = 0;
						for(int i = 0; i < m; ++i) if(t&(1<<i)) parz ^= (a&1)^(i&1);
						
						dp[a+1][b+ile][t][d^parz].fi += dp[a][b][c][d].fi;
						dp[a+1][b+ile][t][d^parz].se += dp[a][b][c][d].se + dp[a][b][c][d].fi*dodaj;
					}
				}
				
				ll mian = 0ll;
				for(int i = 0; i < (1<<m); ++i) mian += dp[n][k][i][0].se;
				cout << mian;
				
				if(k < 8) cout << ",";
			}
			cout << "}";
			if(m < 8) cout << ",";
		}
		cout << "}";
		if(n < 8) cout << ",";
	}
	cout << "}";
	
	return 0;
}
*/