module main; // https://kmjp.hatenablog.jp/entry/2015/12/05/0900 より // 動的計画法 import std; import core.bitop; // https://forum.dlang.org/post/k1js2b$1bef$1@digitalmars.com より // 変数の参照 struct Ref(T) { private T* _payload; this(ref T i) { _payload = &i; } @property ref T deref() { return *_payload; } alias deref this; } auto ref_(T)(ref T arg) { return Ref!T(arg); } // 多次元配列をある値で埋める void fill(A, T)(ref A a, T value) if (isArray!A) { alias E = ElementType!A; static if (isArray!E) { foreach (ref e; a) fill(e, value); } else { a[] = value; } } void main() { // 入力 int H, W; readln.chomp.formattedRead("%d %d", H, W); readln; // 1行読み飛ばす auto P = new double[][](H); foreach (ref p; P) p = readln.split.map!(a => a.to!double / 100).array; readln; auto S = new int[][](H); foreach (ref s; S) s = readln.split.to!(int[]); // 答えの計算 auto memoMask = new int[](1 << (2 * W)), failMask = new int[](1 << W); foreach (mask; 0 .. 1 << (2 * W)) { auto stand = ref_(memoMask[mask]); foreach (j; 0 .. 2) foreach (i; 0 .. W) { int x = j ? i : W - 1 - i; if (((stand >> x) & 1) + ((stand >> (x + 2)) & 1) >= ((mask >> (2 * x)) & 3)) stand |= 1 << (x + 1); } stand >>= 1; } foreach (mask; 0 .. 1 << W) foreach (x; 0 .. W) if ((mask & (1 << x)) == 0) failMask[mask] |= 3 << (2 * x); double ans = 0; auto dp = uninitializedArray!(double[][])(H + 1, 1 << W); fill(dp, 0); dp[0][0] = 1; foreach (y; 0 .. H) { auto p = new double[](1 << W); foreach (cur; 0 .. 1 << W) { double pat = 1; foreach (x; 0 .. W) { if (cur & (1 << x)) pat *= P[y][x]; else pat *= 1 - P[y][x]; } p[cur] = pat; } foreach (up; 0 .. 1 << W) if (dp[y][up] > 1e-12) { int curMask = 0; foreach (x; 0 .. W) { int r = 4 - S[y][x] + ((up >> x) & 1); r = max(0, min(4 - r, 3)); curMask |= r << (2 * x); } foreach (cur; 0 .. 1 << W) dp[y + 1][memoMask[curMask | failMask[cur]]] += p[cur] * dp[y][up]; } foreach (mask; 0 .. 1 << W) ans += dp[y + 1][mask] * popcnt(mask); } // 答えの出力 writeln(ans); }