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;
	}
}