Let It Flow [Facebook Hacker Cup 2018 Round 1 A]

https://www.facebook.com/hackercup/problem/180494849326631/

縦3横Nのボックスがある。
これに┌┐└┘を入れて、左上から右下が連結状態になるようなものは何通りあるか。
ただし、通過できないマスが指定されている。

考察過程

1. いかにもDPって感じがする
2. それと連結DPも思い出す
3. 連結DPまで行かなくても、どのマスが左上と連結かを持っていればいいのでは？
4. いける

解法

動的計画法で解く。
dp[i][j] := i列目まで埋まっていて、j行目が左上と連結な組合せ
遷移を考えると
0行目は1行目に繋げられる。
1行目は0行目か2行目に繋げられる。
2行目は1行目に繋げられる。
これをやっていくだけ。

int N; string G[3];
//---------------------------------------------------------------------------------------------------
mint dp[1010][3];
void solve() {
    cin >> N;
    rep(i, 0, 3) cin >> G[i];
    rep(i, 0, N + 1) rep(j, 0, 3) dp[i][j] = 0;

    dp[0][0] = 1;
    rep(i, 0, N) {
        if (G[0][i] == '.' and G[1][i] == '.') {
            dp[i + 1][1] += dp[i][0];
            dp[i + 1][0] += dp[i][1];
        }
        if (G[1][i] == '.' and G[2][i] == '.') {
            dp[i + 1][1] += dp[i][2];
            dp[i + 1][2] += dp[i][1];
        }
    }

    printf("%d\n", dp[N][2].get());
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) {
        printf("Case #%d: ", t + 1);
        solve();
        fprintf(stderr, "Finish : %d\n", t+1);
    }
}