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
#include <bits/stdc++.h>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

int parity(const vector<string> &board);

bool onBoard(int x, int y, int maxX, int maxY) {
    return x >= 0 and x < maxX and y >= 0 and y < maxY;
}

bool isEmpty(int x, int y, const vector<string> &board) {
    return board[y][x] == '.';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<string> start(n), expected(n);
    for (auto &l : start) cin >> l;
    for (auto &l : expected) cin >> l;
    auto p1 = parity(start), p2 = parity(expected);
    if (p1 != p2) {
        cout << 0 << endl;
        return 0;
    }
    int possibleMoves{};
    int maxX = (int)size(expected[0]);
    int maxY = (int)size(expected);
    int k{};
    for (int y = 0; y < maxY; ++y) {
        for (int x = 0; x < maxX; ++x) {
            if (isEmpty(x, y, expected)) continue;
            ++k;
            for (auto pos : {pair{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}})
                possibleMoves += onBoard(pos.first, pos.second, maxX, maxY) and isEmpty(pos.first, pos.second, expected);
        }
    }

    long long allMoves{};
    if (n == 1) {
        allMoves = 2 * (m - 1);
    } else if (m == 1) {
        allMoves = 2 * (n - 1);
    } else {
        allMoves = 2 * 4 + 3 * (2 * n + 2 * m - 8) + 4 * (n - 2) * (m - 2);
    }
    long long mult = 1;
    for (int i = 0; i < k - 1; ++i) {
        mult *= m * n - 2 - i;
        mult /= i + 1;
    }
    D(
            cerr << "possibleMoves: " << possibleMoves << endl;
            cerr << "mult: " << mult << endl;
            cerr << "allMoves: " << allMoves << endl;
    )
    allMoves *= mult;
    cout << fixed << setprecision(18) << 2 * possibleMoves / (long double)allMoves << endl;
}

int parity(const vector<string> &board) {
    int ret = 0;
    for (int i = 0; i < size(board); ++i) {
        for (int j = 0; j < size(board[i]); ++j) {
            ret += board[i][j] == 'O' and i + j & 1;
        }
    }
    return ret & 1;
}