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
def binomial(n, k):
    if n<0 or k<0 or k>n:
        return 0
    res = 1
    for i in range(1, k+1):
        res *= (n-i+1)
        res //= i
    return res
        

class Epsilon_maker:
    @staticmethod
    def string_to_positioning(board, n, m):
        res = []
        for i in range(n):
            for j in range(m):
                if board[i][j] != '.':
                    res.append((i, j))
        return res
    
    @staticmethod
    def check_parity(pawn_positions):
        res = 0
        for pawn in pawn_positions:
            res += pawn[0] + pawn[1]
        return res%2
    
    def correct(self, x, y, pawn_positions):
        if x >= 0 and x < n and y >= 0 and y < m and (x, y) not in pawn_positions:
            return True
        return False
    
    def get_neighbours(self, pawn_positions):
        moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
        res = 0
        
        for current_pawn in pawn_positions:
            for move in moves:
                new_pawn = (current_pawn[0]+move[0], current_pawn[1]+move[1])
                if self.correct(new_pawn[0], new_pawn[1], pawn_positions):
                    res += 1
        return res
    
    def __init__(self, n, m, pawns):
        self.n, self.m = n, m
        all_elements = [(x//m, x%m) for x in range(0, n*m)]        
        self.all_free_states = 0
        
        for x in all_elements:
            self.all_free_states += self.get_free_states({x}) * (binomial(n*m-1, pawns-1) - binomial(n*m-2, pawns-2))
        self.all_free_states //= 2
                    
    def get_free_states(self, positional):
        return self.get_neighbours(positional)

n, m = [int(x) for x in input().split(' ')]
start = []
end = []
for i in range(n):
    start.append(input())
input()
for i in range(n):
    end.append(input())

proper_start = Epsilon_maker.string_to_positioning(start, n, m)
proper_end = Epsilon_maker.string_to_positioning(end, n, m)

pawns = len(proper_start)
pairwise = Epsilon_maker.check_parity(proper_start)
pairwise_end = Epsilon_maker.check_parity(proper_end)
if pairwise != pairwise_end:
    print(0)

else:
    epsilon = Epsilon_maker(n, m, pawns)
    odds = 1/epsilon.all_free_states
    free_states_end = epsilon.get_free_states(proper_end)

    print(f'{free_states_end*odds:.15f}')