FHC 2018 Round1 A - Let It Flow
問題
タテ3マス・ヨコwマスのグリッドに左上から入り右下から出たい
道は90度曲がったパイプを繋げて作る パイプは回転できる
パイプの繋ぎ方は何通りあるか数える
解法
タテが3マスしかない => 左に戻ることができない
(戻ろうとすると必ずパイプが衝突する)
だから右に進むか上下に進むことだけ考えればよく、そうすればパイプが衝突することもない
int T, w; string s[3]; signed main() { cin >> T; reps(TT,1,T+1) { cin >> w; rep(i,3) cin >> s[i]; int dp[3][1010] = {}; dp[0][0] = 1; rep(j,w) rep(i,3) if (s[i][j]=='.') { if (i%2==0 && s[1][j]=='.') (dp[1][j+1] += dp[i][j]) %= mod; else if (i==1) { if (s[0][j]=='.') (dp[0][j+1] += dp[1][j]) %= mod; if (s[2][j]=='.') (dp[2][j+1] += dp[1][j]) %= mod; } } cout << "Case #" << TT << ": " << dp[2][w] << endl; } }