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
import sys
import numpy
from itertools import combinations
from math import comb

numery_stanu = {}

def numer_stanu(stan):
    if stan not in numery_stanu:
        numery_stanu[stan] = len(numery_stanu)
    return numery_stanu[stan]

def sąsiednie_stany(stan):
    for i in stan:
        if i % szerokość and (i-1) not in stan: # ←
            yield tuple(sorted(set(stan) ^ set((i, i-1))))
        if (i+1) % szerokość and (i+1) not in stan: # →
            yield tuple(sorted(set(stan) ^ set((i, i+1))))
        if (i+szerokość) < szerokość*wysokość and (i+szerokość) not in stan: # ↓
            yield tuple(sorted(set(stan) ^ set((i, i+szerokość))))
        if 0 <= (i-szerokość) and (i-szerokość) not in stan: # ↓
            yield tuple(sorted(set(stan) ^ set((i, i-szerokość))))


wysokość, szerokość = map(int, input().split())

def wczytaj_stan():
    stan = []
    for i in range(wysokość):
        linia = input()
        for znak, nr in zip(linia, range(i*szerokość, (i+1)*szerokość)):
            if znak == 'O':
                stan += [nr]
    return tuple(stan)

stan_początkowy = wczytaj_stan()
input()
stan_końcowy = wczytaj_stan()
#print(stan_początkowy, file=sys.stderr)
#print(stan_końcowy, file=sys.stderr)
pionków = len(stan_początkowy)

stanów = comb(wysokość*szerokość, pionków)

mp = numpy.zeros((stanów, stanów))

for stan in combinations(range(wysokość*szerokość), pionków):
    #print(stan, file=sys.stderr)
    numer = numer_stanu(stan)
    sąsiednie = list(sąsiednie_stany(stan))
    p = 1/len(sąsiednie)
    #print(stan, list(sąsiednie), file=sys.stderr)
    for sąsiedni in sąsiednie:
        try:
            mp[numer, numer_stanu(sąsiedni)] = p
        except IndexError:
            print(numery_stanu)
            raise


m = mp
for i in range(30):
    #print()
    #print(numpy.round_(m, 16), file=sys.stderr)
    m = m @ m
#print(numpy.round_(m, 16), file=sys.stderr)



print(m[numer_stanu(stan_początkowy), numer_stanu(stan_końcowy)])