解答：Submission #19484879 - KEYENCE Programming Contest 2021
解法：空白マスの取扱いが難しい。(1, 1)から(r, c)までの1つのパスを考える。通常このパスは1通りであるが、パス中に空白マスがある場合、この空白マスはXまたは(RもしくはD)の2通りに置き換えることが出来る。また、このパスで通らなかった空白マスについてはX, R, Dの3通りに置き換えることができる。
よって、dp[r][c]を「(1, 1) から(r, c)までのパスの総数」とすると、dp[r][c]はdp[r-1][c] or dp[r][c-1]から遷移するが、空白マスの遷移からは2倍して遷移させ、一方でlを「(1, 1) - (r, c)内空白マスの総数 」、xを「各パスにおける空白マスの数」とし、 各パスごとに3^(l-x)を乗ずる。これは遷移の際に2/3を乗じ、最後に3^lを乗ずるのと同値である。
