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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <cstdio>
#include <algorithm>

int n, m, tk;

char a[16][16];
char b[16][16];

int parityA[3];
int parityB[3];
int all[3];

int vx[4] = {-1, 0, 1, 0};
int vy[4] = {0, -1, 0, 1};

long long memo[65][65];

long long npok(int N, int K) {
  if (N < 0 || K > N) return 0;
  if (K == 0 || K == N) return 1;
  if (memo[N][K] != -1) return memo[N][K];
  return memo[N][K] = npok(N - 1, K) + npok(N - 1, K - 1);
}

int main() {
  for (long long i = 0; i <= 64; ++i) {
    for (long long j = 0; j <= 64; ++j) {
      memo[i][j] = -1;
    }
  }
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) scanf(" %s ", &a[i]);
  for (int j = 0; j < n; ++j) scanf(" %s ", &b[j]);

  parityA[0] = parityA[1] = 0;
  parityB[0] = parityB[1] = 0;
  all[0] = all[1] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      parityA[(i + j) % 2] += a[i][j] == 'O';
      parityB[(i + j) % 2] += b[i][j] == 'O';
      all[(i + j) % 2] += 1;
    }
  }
  if (parityA[1] % 2 != parityB[1] % 2) {
    printf("0.0\n");
    return 0;
  }
  tk = parityA[0] + parityA[1];
  long long cntTotalMoves = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
       if ((i + j) % 2 == 0) {
          for (int free = 0; free < 16; ++free) {
            bool good = true;
            int cntFreeFields = 0;
            int pickBlockers = 0;
            for (int k = 0; k < 4; ++k) {
              if (free&(1<<k)) {
                if (i + vx[k] >= 0 && i + vx[k] < n && j + vy[k] >= 0 && j + vy[k] < m) {
                  ++cntFreeFields;
                } else {
                  good = false;
                }
              } else {
                if (i + vx[k] >= 0 && i + vx[k] < n && j + vy[k] >= 0 && j + vy[k] < m) {
                  ++pickBlockers;
                }
              }
            }
            if (!good) continue;
            for (int W = pickBlockers; W < tk; ++W) {
              if (W % 2 != parityA[1] % 2) continue;
              cntTotalMoves += cntFreeFields * npok(all[1] - cntFreeFields - pickBlockers, W - pickBlockers) * npok(all[0] - 1, tk - W - 1);
      //        printf("W => %d %lld\n", W, cntFreeFields * npok(all[1] - cntFreeFields - pickBlockers, W - pickBlockers) * npok(all[0] - 1, tk - W - 1));
            }
  //          printf("H %d %d %d => %lld\n", free, cntFreeFields, pickBlockers, npok(all[1] - cntFreeFields - pickBlockers, parityA[1] - pickBlockers) * npok(all[0] - 1, parityA[0] - 1));
    //        printf("%d %d %lld\n", all[1] - cntFreeFields - pickBlockers, parityA[1] - pickBlockers, npok(all[1] - cntFreeFields - pickBlockers, parityA[1] - pickBlockers)); 
          }
   //       printf("==== %d %d %lld\n", i, j, cntTotalMoves);
       } else { // == 1
          for (int free = 0; free < 16; ++free) {
            bool good = true;
            int cntFreeFields = 0;
            int pickBlockers = 0;
            for (int k = 0; k < 4; ++k) {
              if (free&(1<<k)) {
                if (i + vx[k] >= 0 && i + vx[k] < n && j + vy[k] >= 0 && j + vy[k] < m) {
                  ++cntFreeFields;
                } else {
                  good = false;
                }
              } else {
                if (i + vx[k] >= 0 && i + vx[k] < n && j + vy[k] >= 0 && j + vy[k] < m) {
                  ++pickBlockers;
                }
              }
            }
            if (!good) continue;
            for (int W = pickBlockers; W < tk; ++ W) {
              if ((tk - W) % 2 != parityA[1] % 2) continue;
              cntTotalMoves += cntFreeFields * npok(all[0] - cntFreeFields - pickBlockers, W - pickBlockers) * npok(all[1] - 1, tk - W - 1);
  //            printf("npok(%d %d %lld)\n", all[1] - 1, tk - W - 1, npok(all[1] - 1, tk - W - 1));
    //          printf("W => %d %d %d %lld\n", W, pickBlockers, cntFreeFields, cntFreeFields * npok(all[0] - cntFreeFields - pickBlockers, W - pickBlockers) * npok(all[1] - 1, tk - W - 1));
            }

  //          printf("H %d %d %d => %lld\n", free, cntFreeFields, pickBlockers, cntFreeFields * npok(all[0] - cntFreeFields - pickBlockers, parityA[0] - pickBlockers) * npok(all[1] - 1, parityA[1] - 1));
          }
//          printf("==== %d %d %lld\n", i, j, cntTotalMoves);
        }
     }
  }

  int cntMoves = 0;

      for (int A = 0; A < n; ++A) {
        for (int B = 0; B < m; ++B) {
           if (b[A][B] == 'O') {
             if (A > 0 && b[A - 1][B] == '.') {
               ++cntMoves;
             }
             if (A + 1 < n && b[A + 1][B] == '.') {
               ++cntMoves;
             }
             if (B > 0 && b[A][B - 1] == '.') {
               ++cntMoves;
             }
             if (B + 1 < m && b[A][B + 1] == '.') {
               ++cntMoves;
             }
           }
        }
      }
//  printf("%d %lld\n", cntMoves, cntTotalMoves);
  printf("%.15Lf\n", (long double)(cntMoves) / cntTotalMoves);

  return 0;
}