wie

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <tuple>
#include <stack>
#include <iomanip>
#include <unordered_map>
#include <bitset>

using namespace std;

// suma mozliwych ruchow ze wszytkich stanow przy danej liczbie pionków rozmiarze planszy,
uint64_t ltable [8][8][8]={
    {
    {0, 2, 4, 6, 8, 10, 12, 14, },
    {2, 8, 14, 20, 26, 32, 38, 44, },
    {4, 14, 24, 34, 44, 54, 64, 74, },
    {6, 20, 34, 48, 62, 76, 90, 104, },
    {8, 26, 44, 62, 80, 98, 116, 134, },
    {10, 32, 54, 76, 98, 120, 142, 164, },
    {12, 38, 64, 90, 116, 142, 168, 194, },
    {14, 44, 74, 104, 134, 164, 194, 224, },

    },
    {
    {0, 0, 4, 12, 24, 40, 60, 84, },
    {0, 16, 56, 120, 208, 320, 456, 616, },
    {4, 56, 168, 340, 572, 864, 1216, 1628, },
    {12, 120, 340, 672, 1116, 1672, 2340, 3120, },
    {24, 208, 572, 1116, 1840, 2744, 3828, 5092, },
    {40, 320, 864, 1672, 2744, 4080, 5680, 7544, },
    {60, 456, 1216, 2340, 3828, 5680, 7896, 10476, },
    {84, 616, 1628, 3120, 5092, 7544, 10476, 13888, },

    },
    {
    {0, 0, 0, 6, 24, 60, 120, 210, },
    {0, 8, 84, 300, 728, 1440, 2508, 4004, },
    {0, 84, 504, 1530, 3432, 6480, 10944, 17094, },
    {6, 300, 1530, 4368, 9486, 17556, 29250, 45240, },
    {24, 728, 3432, 9486, 20240, 37044, 61248, 94202, },
    {60, 1440, 6480, 17556, 37044, 67320, 110760, 169740, },
    {120, 2508, 10944, 29250, 61248, 110760, 181608, 277614, },
    {210, 4004, 17094, 45240, 94202, 169740, 277614, 423584, },

    },
    {
    {0, 0, 0, 0, 8, 40, 120, 280, },
    {0, 0, 56, 400, 1456, 3840, 8360, 16016, },
    {0, 56, 840, 4080, 12584, 30240, 62016, 113960, },
    {0, 400, 4080, 17472, 50592, 117040, 234000, 422240, },
    {8, 1456, 12584, 50592, 141680, 321048, 632896, 1130424, },
    {40, 3840, 30240, 117040, 321048, 718080, 1402960, 2489520, },
    {120, 8360, 62016, 234000, 632896, 1402960, 2724120, 4811976, },
    {280, 16016, 113960, 422240, 1130424, 2489520, 4811976, 8471680, },

    },
    {
    {0, 0, 0, 0, 0, 10, 60, 210, },
    {0, 0, 14, 300, 1820, 6720, 18810, 44044, },
    {0, 14, 840, 7140, 31460, 98280, 248064, 541310, },
    {0, 300, 7140, 48048, 189720, 555940, 1345500, 2850120, },
    {0, 1820, 31460, 189720, 708400, 2006550, 4746720, 9891210, },
    {10, 6720, 98280, 555940, 2006550, 5565120, 12977380, 26762340, },
    {60, 18810, 248064, 1345500, 4746720, 12977380, 29965320, 61352694, },
    {210, 44044, 541310, 2850120, 9891210, 26762340, 61352694, 124957280, },

    },
    {
    {0, 0, 0, 0, 0, 0, 12, 84, },
    {0, 0, 0, 120, 1456, 8064, 30096, 88088, },
    {0, 0, 504, 8568, 56628, 235872, 744192, 1948716, },
    {0, 120, 8568, 96096, 531216, 2001384, 5920200, 14820624, },
    {0, 1456, 56628, 531216, 2691920, 9631440, 27530976, 67260228, },
    {0, 8064, 235872, 2001384, 9631440, 33390720, 93437136, 224803656, },
    {12, 30096, 744192, 5920200, 27530976, 93437136, 257701752, 613526940, },
    {84, 88088, 1948716, 14820624, 67260228, 224803656, 613526940, 1449504448, },

    },
    {
    {0, 0, 0, 0, 0, 0, 0, 14, },
    {0, 0, 0, 20, 728, 6720, 35112, 132132, },
    {0, 0, 168, 7140, 75504, 432432, 1736448, 5521362, },
    {0, 20, 7140, 144144, 1150968, 5670588, 20720700, 61752600, },
    {0, 728, 75504, 1150968, 8075760, 36920520, 128477888, 369931254, },
    {0, 6720, 432432, 5670588, 36920520, 161388480, 545049960, 1536158316, },
    {0, 35112, 1736448, 20720700, 128477888, 545049960, 1803912264, 5010470010, },
    {14, 132132, 5521362, 61752600, 369931254, 1536158316, 5010470010, 13770292256, },

    },
    {
    {0, 0, 0, 0, 0, 0, 0, 0, },
    {0, 0, 0, 0, 208, 3840, 30096, 151008, },
    {0, 0, 24, 4080, 75504, 617760, 3224832, 12620256, },
    {0, 0, 4080, 164736, 1973088, 12961344, 59202000, 211723200, },
    {0, 208, 75504, 1973088, 19612560, 116035920, 495557568, 1691114304, },
    {0, 3840, 617760, 12961344, 116035920, 645553920, 2647385520, 8778047520, },
    {0, 30096, 3224832, 59202000, 495557568, 2647385520, 10565771832, 34357508640, },
    {0, 151008, 12620256, 211723200, 1691114304, 8778047520, 34357508640, 110162338048, },

    },

    };


int64_t ruch(uint64_t plansza, int pozycja,int n, int m){
    //4 normalne ruchy pionka minus liczba kolizji wprowadzamy jesli na planszy postawimy
    //pionek na pozycji. kolizji nie powinno byc wieksze niz 8.
    int aku=0;
    if (pozycja <m )
        aku++;
    else
        if ((1ull<<(pozycja-m))&plansza)
            aku+=2;

    if ((pozycja%m)==0 )
        aku++;
    else
        if ((1ull<<(pozycja-1))&plansza)
            aku+=2;

    if (pozycja >=m*n-m )
        aku++;
    else
        if ((1ull<<(pozycja+m))&plansza)
            aku+=2;

    if ((pozycja%m)==m-1 )
        aku++;
    else
        if ((1ull<<(pozycja+1))&plansza)
            aku+=2;
    return 4-aku;
}

uint64_t dozwolonych_ruchow(  int n, int m, uint64_t plansza, int pozycja, int pionkow, int max_pionkow, uint64_t ruchow ){
    uint64_t aku=0;
    if (pionkow>0){
        ruchow+=ruch(plansza, pozycja,n,m);
        plansza+= (1ull<<pozycja);
    }
    if (pionkow<max_pionkow)
        for (int i=pozycja+1; i<=n*m - (max_pionkow-pionkow); i++ ){
            aku+=dozwolonych_ruchow(n,m,plansza ,i,pionkow+1,max_pionkow,ruchow);
        }
    else{
        aku=ruchow;
    }
    return aku;
}

void generuj_tabelke(){
    // suma mozliwych ruchow ze wszytkich stanow przy danym rozmiarze i liczbie pionkow,
    //do przygotowania magicznej tabelki

    cout<<"{\n";
    for (int pionkow =1; pionkow<=8; pionkow++){
        array<array<int64_t,9>, 9> tab;

        for (int n=1; n<=8; n++){
            for (int m=n; m<=8;m++){
                int64_t wyn = dozwolonych_ruchow(n,m,0,-1,0,pionkow,0);
                tab[m][n]=wyn;
                tab[n][m]=wyn;
            }
        }
        cout<<"{\n";
        for (int n=1; n<=8; n++){
            cout<<"{";
            copy(begin(tab[n])+1,end(tab[n]),ostream_iterator<int64_t>(cout, ", "));
            cout<<"},\n";
        }
        cout<<"\n},\n";
    }
    cout<<"\n};\n";

}

int main()
{
    int inP=0, outP=0;//parzystosci

    int n,m;
    cin>>n>>m;
    if (n==42){// :)
        generuj_tabelke();
        return 0;
    }

    int pionkow =0;

    for (int y=0; y<n; y++){
        for (int x=0; x<m;x++){
            char c;
            cin>>c;
            if (c=='O'){
                inP = (inP + y + x )%2;
                pionkow++;
            }
        }
    }
    int64_t ruchow=0;
    uint64_t plansza=0;
    int pozycja =0;
    for (int y=0; y<n; y++){
        for (int x=0; x<m;x++){
            char c;
            cin>>c;
            if (c=='O'){
                outP = (outP + y + x )%2;
                ruchow += ruch(plansza, pozycja, n,m);
                plansza+= (1ull<<pozycja);
            }
            pozycja++;
        }
    }

    if (inP==outP){
        cout<< std::fixed << std::setprecision(15) <<  ruchow*2.0 / (double)ltable[pionkow-1][n-1][m-1]<<endl;
    }else
        cout<<0<<endl;

    return 0;
}