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
import time
from collections import Counter

PAWN = 'O'
EMPTY = '.'


def board_to_str(a):
    return "\n".join("".join(row) for row in a)

def clone_board(a):
    return [[e for e in s] for s in a]


def to_tuple(a):
    return tuple(tuple(e for e in s) for s in a)


def from_tuple(t):
    return [[e for e in s] for s in t]


dxs = [-1, 0, 1, 0]
dys = [0, 1, 0, -1]


def gen_moves(a):
    n = len(a)
    m = len(a[0])
    res = []
    for i in range(n):
        for j in range(m):
            if a[i][j] == PAWN:
                for dx, dy in zip(dxs, dys):
                    ni = i+dx
                    nj = j+dy
                    if ni >= 0 and ni < n and nj >= 0 and nj < m and a[ni][nj] == EMPTY:
                        b = clone_board(a)
                        b[i][j], b[ni][nj] = b[ni][nj], b[i][j]
                        res.append(b)

    return res


n, m = map(int, input().split())
a_init = []
a_target = []
for i in range(n):
    a_init.append(list(input().strip()))

s_empty = input()

for i in range(n):
    a_target.append(list(input().strip()))


mem = {to_tuple(a_init): 1.0}


def make_step():
    global mem
    next_mem = {}
    for t_a, p in mem.items():
        a = from_tuple(t_a)
        moves = gen_moves(a)
        for b in moves:
            t_b = to_tuple(b)
            if t_b not in next_mem:
                next_mem[t_b] = 0
            next_mem[t_b] += p * (1.0 / len(moves))
    mem = next_mem


def run_steps(n_steps):
    assert n_steps % 2 == 0
    for i in range(n_steps):
        make_step()


def run_time(t_limit, n_steps):
    global mem
    t_stop = time.time() + t_limit
    cnt_steps = 0
    while True:
        if time.time() > t_stop:
            if cnt_steps % 2 == 1:
                make_step()
            break
        make_step()
        cnt_steps += 1
        if cnt_steps == n_steps:
            break


#run_steps(10000)
run_time(0.10, n_steps=5000)
#run_time(30, n_steps=5000)


cnt = {}
for a, p in mem.items():
    #print(a, round(p, 5))
    p_r = round(p, 5)
    if p_r not in cnt:
        cnt[p_r] = []
    cnt[p_r].append(a)

if False:
    for p, boards in sorted(cnt.items(), key=lambda e: e[0]):
        print(p, len(boards))
        for b in boards:
            b_s = board_to_str(b)
            #print("###")
            #print(b_s)
            #print("###")
#print("####################################")
#print(cnt)

#print("####################################")
t_target = to_tuple(a_target)
res = mem.get(t_target, 0)
print('{0:.15f}'.format(res))