Submission

Score: 20

User: kormuyang

Problemset: ทางเชื่อม

Language: cpp

Time: 0.102 second

Submitted On: 2025-12-15 12:15:24

/*
TASK: bridge
LANG: C++
AUTHOR: YourName YourLastName
CENTER: SUT
*/
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MOD = 1000000007;

void solve() {
    int N;
    // Check if input exists to avoid runtime errors
    if (!(cin >> N))
        return;

    // Loop through each test case (Pattern)
    while (N--) {
        int L;
        cin >> L;

        string row1, row2;
        cin >> row1 >> row2;

        // dp[0] represents ways ending at the Top row
        // dp[1] represents ways ending at the Bottom row
        // Initial state: 1 way to enter Top, 1 way to enter Bottom from the far left
        long long dp0 = 1;
        long long dp1 = 1;

        for (int i = 0; i < L; ++i) {
            bool free_top = (row1[i] == '.');
            bool free_bot = (row2[i] == '.');

            long long next_dp0 = 0;
            long long next_dp1 = 0;

            // Calculate ways to reach the Top cell of current column
            if (free_top) {
                // Straight from previous Top
                next_dp0 = (next_dp0 + dp0) % MOD;

                // Cross from previous Bottom (Requires both cells in current column to be free)
                if (free_bot) {
                    next_dp0 = (next_dp0 + dp1) % MOD;
                }
            }

            // Calculate ways to reach the Bottom cell of current column
            if (free_bot) {
                // Straight from previous Bottom
                next_dp1 = (next_dp1 + dp1) % MOD;

                // Cross from previous Top (Requires both cells in current column to be free)
                if (free_top) {
                    next_dp1 = (next_dp1 + dp0) % MOD;
                }
            }

            // Update DP table for the next iteration
            dp0 = next_dp0;
            dp1 = next_dp1;
        }

        // The answer is the total valid paths reaching the end (either Top or Bottom)
        cout << (dp0 + dp1) % MOD << endl;
    }
}

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}