#include #include #include #include using namespace std; constexpr double eps = 1e-20; int R = 0; int C = 0; double solve(const int R, const int C, const vector> & P, const vector> & S); int get_next_status(int prev, int know, const vector & s); double calc_prob(int mask, const vector & p); int bitcount(int mask){ int counts = 0; while (mask){ if (mask & 1) ++counts; mask >>= 1; } return counts; } template void disp(const vector< vector > & mat){ for (const auto & row : mat){ for (const auto elem : row){ cout << elem << ' '; } cout << endl; } } int main() { cin >> R >> C; vector< vector > S(R, vector(C, 0)); vector< vector > P(R, vector(C, 0.0)); // read data for (auto & row : P){ for (auto & p : row){ cin >> p; p /= 100.0; } } for (auto & row : S){ for (auto & s : row) cin >> s; } // solve cout << solve(R, C, P, S) << endl; return 0; } double solve(const int R, const int C, const vector> & P, const vector> & S){ double ans = 0; vector old_prob(1 << C, 0.0); vector new_prob(1 << C, 0.0); old_prob[0] = 1.0; for (int r = 0; r != R; ++r){ auto s = S[r]; auto p = P[r]; for (int prev = 0; prev != 1 << C; ++prev){ auto old_p = old_prob[prev]; if (old_p <= eps) continue; for (int know = 0; know != 1 << C; ++know){ auto new_p = calc_prob(know, p); auto new_status = get_next_status(prev, know, s); new_prob[new_status] += old_p * new_p; } } for (int status = 0; status != 1 << C; ++status){ ans += new_prob[status] * bitcount(status); } swap(old_prob, new_prob); for (auto & np : new_prob) np = 0; } return ans; } double calc_prob(int mask, const vector & p){ double prob = 1.0; for (auto pi : p){ prob *= (mask & 1) ? pi : (1 - pi); mask >>= 1; } return prob; } int get_next_status(int prev, int know, const vector & s){ // prev & (1< points(C, 0); deque changed; for (int i = 0; i != C; ++i){ if (prev & (1<= 4) changed.push_back(i); } while (not changed.empty()){ auto i = changed.front(); changed.pop_front(); if (i){ points[i - 1] += 1; if (points[i - 1] == 4) changed.push_back(i - 1); } if (i < C - 1){ points[i + 1] += 1; if (points[i + 1] == 4) changed.push_back(i + 1); } } int ans = 0; for (int i = 0; i != C; ++i){ if (points[i] >= 4) ans += (1<