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
#include <iostream>
#include <vector>
#include <utility>
#include <iomanip>

namespace {
    using std::cin;
    using std::cout;
    using std::move;
    using row_t = std::vector<size_t>;
    using pawns_t = std::vector<row_t>;

    constexpr char O = 'O';
    constexpr char N = '.';
    constexpr double REPETITIONS = 100000.0;

    void load_pawns(pawns_t & pawns, size_t n, size_t m) {
        char s;
        for (size_t i = 0; i < n; ++i) {
            row_t row{};
            for (size_t k = 0; k < m; ++k) {
                cin >> s;
                if (s == O)
                    row.push_back(k);
            }
            pawns[i] = move(row);
        }
    }

    bool compare_pawn_rows(
            pawns_t const & pawns, pawns_t const & dest_pawns
    ) {
        for (size_t k = 0; k < pawns.size(); ++k)
            if (pawns[k].size() != dest_pawns[k].size())
                return false;
        return true;
    }

    bool no_move_rows(pawns_t const & pawns, size_t m) {
        for (size_t k = 0; k < pawns.size(); ++k)
            if (pawns[k].size() > 0 && pawns[k].size() < m)
                return false;
        return true;
    }

    void pawn_move(pawns_t & pawns, size_t m) {
        size_t r_row;
        do {
            r_row = rand() % (pawns.size());
        } while (pawns[r_row].size() == 0 || pawns[r_row].size() == m);
        size_t r_idx = 0;
        size_t r_col = pawns[r_row][r_idx];
        if (pawns[r_row].size() > 1) {
            do {
                r_idx = rand() % pawns[r_row].size();
                r_col = pawns[r_row][r_idx];
            } while (
                (r_col == 0 && pawns[r_row][r_idx + 1] == 1)
                || (r_col == m - 1 && pawns[r_row][r_idx - 1] == m - 2)
                || (r_col > 0 && r_col < m - 1 && pawns[r_row][r_idx - 1] == r_col - 1
                    && pawns[r_row][r_idx + 1] == r_col + 1)
            );
        }

        if (r_col == 0 || pawns[r_row][r_idx - 1] == r_col - 1) {
            pawns[r_row][r_idx] = r_col + 1;
        } else if (r_col == m - 1 || pawns[r_row][r_idx + 1] == r_col + 1) {
            pawns[r_row][r_idx] = r_col - 1;
        } else {
            pawns[r_row][r_idx] = r_col + (rand() % 2 == 0 ? 1 : -1);
        }
    }

    bool check_destination(pawns_t const & pawns, pawns_t const & dest_pawns) {
        for (size_t k = 0; k < pawns.size(); ++k)
            for (size_t l = 0; l < pawns[k].size(); ++l)
                if (pawns[k][l] != dest_pawns[k][l])
                    return false;
        return true;
    }
}

int main() {
    size_t n, m;
    cin >> n;
    pawns_t pawns(n);
    pawns_t dest_pawns(n);
    cin >> m;
    load_pawns(pawns, n, m);
    load_pawns(dest_pawns, n, m);

    size_t drawn_dest = 0;
    if (m > 1 && compare_pawn_rows(pawns, dest_pawns)
        && !no_move_rows(pawns, m)) {
        for (size_t r = 0; r < REPETITIONS; ++r) {
            pawn_move(pawns, m);
            pawn_move(pawns, m);
            if (check_destination(pawns, dest_pawns))
                ++drawn_dest;
        }
    }

    cout << std::setprecision(2) << drawn_dest / REPETITIONS << '\n';
    return 0;
}