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 <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>

using namespace std;

const int MAXN = 8;

//#define NDEBUG

int n,m;
#define ENCODE(row, col) (row*8+col)
#define DECODECOL(encoded) (encoded % 8)
#define DECODEROW(encoded) (encoded / 8)

void explore(map<set<int>, double>prob[2], int depth, set<int> init);

bool movepossible(set<int> &state, int newstate) {
	return state.count(newstate) == 0;
}

void explorerecurse(map<set<int>, double>prob[2], int depth, int oldstate, int newstate, set<int> &state, double addprob) {
	set<int> newset(state);
	newset.erase(newset.find(oldstate));
	newset.insert(newstate);
	bool explored = prob[(depth+1)%2].count(newset) > 0;
	prob[(depth+1)%2][newset] += addprob;
	if (!explored) {
		explore(prob, depth+1, newset);
	}
}

void explore(map<set<int>, double>prob[2], int depth, set<int> init) {
	double addprob = prob[depth%2][init];
	queue<pair<int,int>> possible_moves;

	for (auto it = init.begin(); it != init.end(); ++it) {
		int col = DECODECOL(*it);
		int row = DECODEROW(*it);
		if (col + 1 < m) {
			int newstate = ENCODE(row, col+1);
			if (movepossible(init, newstate)) {
				possible_moves.emplace(*it, newstate);
			}
		}
		if (col - 1 >= 0) {
			int newstate = ENCODE(row, col-1);
			if (movepossible(init, newstate)) {
				possible_moves.emplace(*it, newstate);
			}
		}
		if (row + 1 < n) {
			int newstate = ENCODE(row+1, col);
			if (movepossible(init, newstate)) {
				possible_moves.emplace(*it, newstate);
			}
		}
		if (row - 1 >= 0) {
			int newstate = ENCODE(row-1, col);
			if (movepossible(init, newstate)) {
				possible_moves.emplace(*it, newstate);
			}
		}
	}
	if(!possible_moves.empty()) {
		addprob /= possible_moves.size();
	}
	while (!possible_moves.empty()) {
		explorerecurse(prob, depth, possible_moves.front().first, possible_moves.front().second, init, addprob);
		possible_moves.pop();
	}
}

int main() {
	map<set<int>,double> prob[2];
	char c;
    scanf("%d%d", &n, &m);
	set<int> state, target;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			scanf(" %c", &c);
			assert(c == '.' || c == 'O');
			if (c == 'O') {
				state.insert(ENCODE(i, j));
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			scanf(" %c", &c);
			assert(c == '.' || c == 'O');
			if (c == 'O') {
				target.insert(ENCODE(i, j));
			}
		}
	}
	prob[0][state] = 1.;
	explore(prob, 0, state);
	printf("%F\n", prob[0][target]*2);
}